The specific form of the word in Latin and English is mediaeval, but it draws on much older concepts and constructs on other languages.
Two thousand years ago, εγκυκλιος παιδεια ("enkyklios paideia") would refer to a concept called "orbis doctrinae" in mediaeval Latin, i.e., to a something that would be called "general education" today - a standardized set and depth of disciplines necessary for the education of a well rounded member of the aristocratic elite of the society.
The Greek εγκυκλιος had several meanings that I'm having difficulty tracing to any particular timeline: a circle, anything that keeps revolving or moving with regularity, anything that keeps recurring at regular times. An important additional meaning is "general". Whether this last meaning is connected to the tendency (of particular knowledge) to be encountered recurrently, or rather to the sense of being continuously shared with "other people around oneself", or some yet other semantic development, I can't tell.
As an aside, the etymology of the Latin "orbis" isn't entirely clear either, but its semantic development does not seem to parallel the Greek word. "Orbis" seems to have started from a meaning of a "circle", with a specialized meaning of the (round) world, eventually applied metaphorically as the "whole world of..." or "the whole of..."
A strange thing happened when "enkyklios paidea" ended up borrowed into late mediaeval Latin which didn't quite need a new word at the time. The Greek phrase was incorrectly interpreted as a single word in Greek and the Latin term "encyclopaedia" was used ad hoc to "render" it in translation. The accidentally created word gradually caught on and it eventually, centuries later, acquired a stable meaning of its own. The Latin cyclus, which was undoubtedly informing the interpretation of this rather unfamiliar new Latin word during the 15th and 16th centuries within Latin, shares the meaning of "circle" and the meaning of "regularly recurring" with Ancient Greek κυκλος, but not the Ancient Greek meaning of "general".
In some sense, therefore, the meaning of "general" was associated with the phrase long before the meaning of "a circle" was. However, the entire phrase wasn't referring to a literary genre in Ancient Greek, but rather to an abstract body of knowledge, or to an abstract, ideal curriculum for education of young people.