Below the surface world, lies a completely different realm.
A vast network of caves, caverns and tunnels runs under much of the lands occupied by the Eastern peoples and the Empire. Some tunnels run for hundreds of miles, connecting caverns big enough to hold cities. Underground lakes and rivers form vast water systems.
Much of the underworld has been formed naturally. The unique and mostly stable geology of the continent has allowed water to carve out spaces over millions of years. There are areas, particularly deeper in the underworld, that appear to have been made by vast, rock eating worms. What they were and where they went is unknown.
The Fay discovered the Underworld and used it extensively. All the industrial and magical processes they did not want polluting the surface world they buried underground. Either making use of the existing caverns or creating new ones. They also made new slaves, Dwarfs and Gnomes, specifically to construct there sub-terrain settlements.
Typically these mines and factories where run by a small number of Fay who lived in palatial apartments. Often with large gardens and parks to give them some semblance of the surface worlds. Doing all the hard work were gem slaves of many different races.
As the disease of life spread and the rebellion took hold, surface cities were no longer safe. Many of the underground settlements were quickly expanded to hold tens of thousands of refuges. The slaves could no longer be trusted and were replaced by the Goblinoid races. These living creatures with free will were carefully engineered to be spiteful and submissive to brute force. To apply that force, devils were created.
The goblinoid races proved a lot less efficient than the non-living, automaton like gem slaves and the fate of the Fay was sealed as production from their mines and factories steadily dropped. No longer did the Fay have the resources to maintain its people and fight a long war against the rebellion.
In the desperate last years of the Fay they bred many strange creatures. Magically merging horses, eagles, humans and lions to create centaurs, hippogriffs, owlbears and many other beasts. These grotesque cross-breeds were the tip of the iceberg and many, many strange and terrible monsters were conjured up by the great wizards of the Fay.
As each underground Fay settlement fell to the rebellion or collapsed from lack of food, the goblinoids and monsters broke loose. Many populating the vast underworld or operating around the junction between the surface and the underground. The old Fay settlements were shunned and slowly lost to time. Only the devils and a handful of the most perverse of the Fay creations are found in these ruins.