Ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn.
In his house at R'lyeh, dead Cthulhu waits dreaming.
R'lyeh is a nation of alien creatures who worshiped the Void. Their homeworld was destroyed in a great cataclysm and one of their homeworld's shards with the Great City of R'lyeh on it fell through the Sphere finally landing in an ocean. The impact destroyed the ancient empire of the Aboleths. The Starspawn of R'lyeh used their great mental power to enslave various native creatures of the seas. They wield armies of slave troopers, Starspawn warriors with Mind Blast and bizarre void creatures. The Starspawn are powerful Astral mages and the Starspawn priests can enter the Void Gate to summon void creatures that are Sacred to the people of R'lyeh. The coastal forts of R'lyeh generate half-human hybrids for free. R'lyeh starts the game underwater; however, with judicious use of amphibious troops they need not confine themselves to the sea.
Time of Aboleths (Early Age)
Before the Great City fell and destroyed their capital, the Aboleths ruled the seas. While the bulk of R'lyeh's armies are still shambler and Atlantean slaves, their elite units and commanders are Aboleths of various ages. The oldest Aboleths are extremely skilled in both water and astral magic.
Fallen Star (Middle Age)
The Great City of R'lyeh fell on an ocean of a new planet. The Starspawn adapted and now they plan the conquest of this world. The armies of R'lyeh are filled with Deep Ones and Shambler Slaves.
Starspawn are large amphibious humanoids with the ability to blast lesser beings' minds from afar. Their mages are strongest in water and astral magic, although earth and death are not too unusual. They also have numerous hybrid and enslaved troops, including Starspawn assassin-mages. They rely on these slaves and hybrids for melee, with the Starspawn remaining safely behind the lines dominating weaker minds.
Dreamlands (Late Age)
The Void pushes further into reality.
The dominion now slowly kills the population. It also lures dreamers and madmen into the pretender's service, while driving non-Void units insane. Commanders may have their periods of lucidity, but the longer they spend in the dominion, and the weaker their minds, the more likely they'll have spent at least some of their time behaving very oddly. This goes for both friendly and enemy commanders; even pretenders are not necessarily immune.
The Void Gate is still present, of course. However, the presence of the Void is everywhere; in fact, void units have been known to appear far from the gate, within the pretender's dominion...
For background material and inspiration, see many of the tales authored by Howard Phillips Lovecraft. Those books are good examples:
This author posits that an imprisoned or sleeping god would be extremely thematic, for those times before The Stars Are Right.
While a very modern mythos, compared to the systems inspiring some of the other nations, this has inspired not only other authors (such as August Derleth) but pencil-and-paper games, board games, a variety of odd merchandise, and even a musical titled 'Shoggoth on the Roof'.