Why do you think Europe "lagged so badly" during the Early Medieval Period? In terms of agriculture, metallurgy, architecture, and many of the sciences, Medieval Europe made vast advances on Rome. Many of the problems faced in the Early Medieval Period in much of Europe were the results of population collapse, plague, civil war and massive recession during Late Antiquity rather than a lack of reading material.

I'd recommend this excellent answer by /u/Astrogator which looks at literacy levels in Rome, and the divide between functional literacy, and the consumption of books.

The problem with this theory is that by the final dissolution of the Western Roman Empire in late 5th/early 6th century, parchment has been in use for at least few centuries both in Rome and other areas. As evidenced by the Cairo Book of the Dead dated to 2nd century BCE, it has been known and used in Egypt, although it did not gain much popularity there.

According to Pliny the Elder, introduction of parchment is a result of the decree of Ptolemy V who forbade export of papyrus and the subsequent adoption of animal leather as the writing material by Eumenes II, king of Pergamon. This information is not well corroborated, however, but the reign of Ptolemy V and Eumenes II largely coincides with relatively widespread adoption of parchment in the Mediterranean area (what means it must have likely started substantially earlier). Since the 2nd century BCE, parchment and papyrus are used concurrently, what in some areas will continue for the next millennium, as the papal curia used papyrus as late as early 11th century. It is worth noting that at that time, parchment was the most common writing material in Europe and paper became slowly adopted in the areas under strong influence of Arabic culture, as Arabs started to produce paper since 8th century, although it became popular in Christian world only five centuries later. On the other hand, after Arab expansion in early 7th century, mass production of papyrus in Egypt was continued, with Lombard and Frankish kingdoms being large importers until widespread adoption of parchment.

It is worth mentioning that parchment, although commonly considered 'crude' or 'less sophisticated' counterpart to the papyrus, had a lot of advantages over its Egyptian predecessor. Parchment was much more durable and had generally lighter shade and smoother surface, what not only had aesthetic value, but allowed for intricate illuminations. Another important advantage was the access to the resources, as the cultivation of papyrus reed (Cyperus papyrus) was possible only in sunny wetlands, a biome not common in Europe and largely nonexistent in its northern half. Furthermore, extensive waterworks near the shoreline of Egypt cause the salination level of Nile to increase, causing many locations to become ineligible for papyrus cultivation, decreasing production output. Parchment, on the other hand, was made from animal hides and as it happened, Europe was very well suited for animal herding and thus parchment could have been sourced pretty much anywhere, alleviating the relatively high unit cost in comparison with papyrus. Additionally, parchment produced in northern part of Europe was made from thicker hide that was smoothed on both sides, doubling the writing surface and allowing for double-sided writing and publication in form of codex (i.e. book with a spine rather than scroll). Last but not least, parchment, due to its thickness, could have been scrubbed with an abrasive tool and re-used, which trait has been quite frequently used, especially in the early Middle Ages, when the infrastructure and thus the supply of the materials still left much to be desired. Thus, from the European perspective, parchment was more desirable than rare, fragile, dark and uneven papyrus. Of course, parchment has been eventually displaced by paper, but that's another story.

Also, it is a common mistake to assume that Europe 'lagged' behind for some reason or that it lived through the a period of diminished development throughout Middle Ages in comparison with the first five centuries of the Common Era. In reality, Middle Ages are a period of a constant development, especially of the areas than were never influenced by the Roman culture to a significant extent. In addition to what u/BRIStoneman wrote, one needs to remember that the Middle Ages ended with the entire Europe being developed to a point hardly achievable in Imperial Rome, even though in portions of Europe were not yet inhabited in the latter period. Sure, the Apeninian Peninsula and surrounding region suffered, but the Eastern Roman Empire remained strong for many centuries and the 'barbarians' developed their own culture that was no less sophisticated than Roman, Greek or Egyptian one. Please note that the Christianity, a carrier of the culture that often introduced writing into the areas not using one finally spread into the last parts of Europe only in mid-11th century (and eventually influenced entire Europe and beyond, a feat no one before that point was able or willing to do). It matters little what writing material is available to a given culture, if that culture does not know writing. And when it adopts this skill, it will be able to find a way to disseminate writing texts, regardless if they need to use reeds, hides, wax, stone, clay, planks, string or bark.

EDIT: Several typos and grammar errors.