What about if the PC find the bugs in some loot? maybe an ancient treasure form a lost port, maybe a burial chamber. They could see that a plague is developing wherever they go, but not know why or how, this could be through rumors and at every tavern, they would hear that the last place they visited has been quarantined because of a mysterious plague!
Perhaps the eggs only kill when they hatch, and one of them is infected, giving them very little time to get to Marlifus... Go to Comment
Gives it an almost Alien movie type surroundings. The cocoons could be skattered all over and not much is remarked about them at first till they get deeper inside. Maybe the cocoon stages make them resistant to most weapons so they can't get inside them at first to see what they actually are. They never knowing what they really are until they start hatching. By then they are already deep inside the catacombs and must go back past all the now hatching cocoons to escape. Go to Comment