Contrary to the name, the Catacombs never started out being graves or tombs. The origin of the Catacombs can be said to have begun when the waste dinhal from Sinkamma permeated into Syrellia's foundations.
The result was that the ground below the city gave way, weakening as the toxic waste magic ate away at the soil, turning it into nothing more than what could be called poisonous sludge. Many of the creatures that roamed outside the city's borders (because that time neither Illudois nor Talathir existed then) and those that resided underground were also poisoned. Many of the creatures died, but those that didn't went on to mutate and grow into the many grotesque monsters found in the Catacombs today.
As for the ground, much of the soil around Syrellia's foundations have long since been eroded by the dinhal. With the introduction of the Halaian trees, the ground has been purified - but there is no way the massive caverns below the city can ever be healed. The scars will remain forever.
The space below the city is vast, almost as wide as the city itself. The inhabitants of Illudois have taken to preventing the spread of the beasts that now reside in the Catacombs.
For reassurance, the Catacombs are at least 20 feet below the surface. The height of the space can vary - around the area of the Illudois workshops, the ceiling is around 10-17 feet, while some places can be at least 30 feet deep and others being a scarce 3 feet. The ecology of the Catacombs is complex to understand - almost all the creatures underground are carnivorous due to the lack of sunlight (complete nonexistence of plants). Those that aren't are usually fungivores, but there are very few. Fortunately, these creatures are sensitive to light, heat and steam, which the engineers of Scientia Nouveau utilise to great effect.
After the Ghosts of SyrelliaEdit
Due to baby dragons diverting themselves into Syrellia during the Dragonflight, the leaders of Syrellia were advised to investigate the source of the magic that caused them to divert in the first place, located deep beneath the Catacombs. The expedition's discovery was that the Catacombs monsters developed due to the power of a mysterious blue crystal resting in the foundations of the city, most likely to a self-defence mechanism to protect itself.
The crystal has not been moved from its place, but the district of Sinkamma (above which the crystal rests) has devised technology that will reduce the amount of magic emitted through the ground so that the dragon hatchlings do not get lost during the Dragonflight again.