When I'm not writing about games or being a trainer, I'm also an ESL teacher. Recently I had a couple students come to me with projects on the pyramids.* Pyramids are a good example of how megadungeons can come about.
I'll skip Why, because Why influences the game very heavily. Let's look at a bit of how, and what that can give you in terms of detail.
How did they build it? Usually the explanation involves magical stone-shaping, strange subterranean races, and mystical gobbledegook. However, like the pyramids, a megadungeon can simply be a straight up application of a magical formula: manpower + a guiding intent + time = lots of work completed. If someone with enough resources and enough will to apply them gets folks digging, you can get a pretty big hole. Looking at a megadungeon from the perspective a long-term project.
It's how Stonehell got built - stick enough people in a small set of tunnels and tell them to dig, and you'll get a big set of tunnels.
If your dungeon was dug out as a big project, you're likely to find some these little bits:
Dungeon Graffiti - Dungeon builders will not just leave mystic marks of their passing, but also marks about who built it. You'll get work crews signing their names, leaving their marks - they find a lot of this stuff in pyramids. Why not in megadungeons, stuck behind some door or on top of a lintel, or behind that giant idol that was put in at the end? Not all "kilroy" marks will be adventurers or monsters - some can be from its initial construction days.
Dungeon Construction Marks - You may even find official marks - an "Inspected by 34" note or a stamp or seal to denote when a section was considered done. Faded paint or ink marks to show what's behind something (like road workers leave when finished doing sewer work.) Doors on man-made levels might have specific marks or types to show you what's in the room beyond. My own Felltower has some storerooms, and near one set there were still wall sections marked with cryptic content marks, for easy inspection. The marks were wrong, by the by, but it made it clear what the rooms were originally.
Incidentally you won't find a lot of "finished" marks near a partially done section - so if PCs learn these they can tell a collapsed area from a never-finished area.
Builder Trash - Broken pottery from packed lunches and drinks shows up near pyramids, but not in them. Fair enough, you won't leave trash behind in a sacred tomb. Nearby is fine - and megadungeons are often presented as a complex of sections. So you might find disused staging areas with broken bits of trash, odd bits of what seem like useless materials, etc. meant for digging. It might even show up on the surface, in trash heaps used when disposing of talus and debris and corpses (if the workers were unvalued slaves instead of volunteers or paid workers). Not much loot, there, perhaps, but good color for "how was this done?" Nothing says hard work like centuries of piled up beer bottles near the dungeon.