10 million years is a geologic-level time scale - so if you truly want a structure to last the ages, then we're going to need some help...specifically, from geology itself.
First, let's consider just how long 10 Ma really is:
So we need something that will last approximately three Epochs...wow, this is going to be epic!
As a matter of fact, this is beyond human time:
That's right, this is about 5 times longer than our closest biological ancestors were even alive...no homo. (rim shot, please, Paul)
But we're in luck because there indeed structures that are approximately this old, or even older - caverns and cave systems!
The Jenolan Caves are considered to be hundreds of millions of years old, but they are also very wet, which will tend to make keeping things intact likely more difficult than in drier conditions. The Grand Canyon Caverns claims to be much younger, perhaps only around a few million years old in its present form, but it's also dry! Water is so good at eroding things, that I'd likely want to pick such a place to build - you can always drill to get access to the water table if you want, and it's easier to control than having it leak in all over the place.
The beauty of caves is that they provide a world that seems relatively unchanging compared to the surface - as long as it doesn't get buried beneath mile-thick ice sheets during an ice age, or have the tectonic plates shift so much that it screws the place up by flooding it or filling it with toxic/explosive gases, you'll be fine!
The natural environment of caves is so good at preserving things that things that died tens of thousands of years ago leave perfectly nice collections of bones. In some cases, the preservation is so good that scientists have managed to extract significant amounts of DNA from animals that have been dead/extinct for many thousands of years - and no one was even trying to preserve these things! The work of the pyramids seems so small compared to what our natural environment can do all by itself sometimes, doesn't it?
This doesn't necessarily have to be a city for mole-people, though. There's no reason such a system couldn't be worked to have a number of "natural entrances", and people could conduct all sorts of outdoors activities. But if such a place existed there would be a strong incentive to develop underground living to a fine art and science, though.
What caves buy you is something you need - protection from the elements. Otherwise, we don't really have any non-exotic substance that can last so long against the weather alone, and if we did it would need regular refurbishing/maintenance that is going to require high technology.
What I like about caves is that progressive levels of technology could be needed to work/live/survive deeper and deeper recesses of the caves. If your people 'forget' how to make the mixture that goes into the UV light fixtures, or maintain the clean air systems, or operate the airlock/airway systems that allow access to the mines or geothermal vent forges, or stop maintaining the water-control systems so they flood lower levels...then the city doesn't get wiped out! They just begin to lose access to the higher-technology awesome stuff that is only possible to enjoy with higher technology.
In theory, even an ancient people with little or no technological understanding could live in the cave systems, even if they have become unable to do the things necessary to navigate, survive, and fully enjoy subterranean living.
With some maintenance, only your imagination is the limit - there are no unsolvable problems deep down. You can grow things, mine things, gather raw materials...the technology level used would be up to your civilization to determine. Want robotic-level automated facilities? Have them conduct their own maintenance, and perhaps only leave material gathering to humans if you don't want robots running around topside. Have big, gorgeous diamond/sapphire-coated representations of the raw materials needed by the deeper inner-workings to label the "inboxes". The humans just put the iron ore in the bin, wood in another bin, bones in another bin, etc, and the system handles the rest.
How you want your story to go would, of course, depend on how the system was crafted and what the exposed/moving parts would be. A semi-autonomous automated system isn't completely out of our current technological abilities, so if this was built by a more advanced race they'd certainly be able to figure out auto-factories that can keep themselves going so long as they are provided with acceptable parameters. Make these inputs or environmental parameters the rules of the city, and so long as the inhabitants keep up their end of the bargain the system works. If they stop the system can have cascading levels of shutdown, ultimately having a core that survives on only the smallest amount of inputs, and designed to safely put itself in permanent hibernation if the final ingredient is no longer provided (your pick on what that might be - nutrient solution, sugar, blood, electricity, light, radioactive materials, whatever).
The biggest danger will be dealing with people, then, screwing with things they shouldn't or not following the rules. Geological changes will cause issues, but an advanced race should be able to understand/predict with some reasonable degree of accuracy what might happen and plan a location or operating parameters that would deal with such a problem - they'll avoid systems that can be flooding with a shifting water table or areas likely to be buried under ice sheets unless the system can support people with no access to the outside, etc. Could be like a big bomb-shelter, or they could just ensure the build was in a place that they felt wouldn't face this problem.
One note, though - over this period of time the people who first lived in the city or designed it will be different biologically over this time period. If people live inside most of the time or even all of it, there will surely be significant biological and psychological/culture changes over such a stretch of time, and so the people might be as different from their origins as we are from our non-bipedal ancestors (walking on two legs is believed to have started around 6 million years ago in human ancestral lines).
That said, there's a crazy amount of possibilities there, and none of it requires magic! How you'll keep people from blowing it up, drilling into the wrong parts, etc, I don't know - but that's not the question. So enjoy!