[Taqwus]

My main concern with R'lyeh would be scalability. Most of their troops (just about everything but hybrids and star children) can only be recruited either underwater or at certain magical sites (and while there's at least one land-based site that provides Void Summoning, it is/they are rather rare), plus the better ones are magical and require magical leadership.
Protecting territory of decent size on land thus depends on independent units, which may have trouble dealing with the better nationals from other nations e.g. hoplites, Emerald Guard, massed xbows + Flaming Arrows et al. The magical nature of their units also makes them highly vulnerable to non-astral leader-killing tactics, because without mages most of their units will rout or even dissolve, and many indy provinces can't produce mages even with a lab. Risky.
Another bit would be that on high-indy settings, sea expansion is _painful_. It takes a lot of chaff to absorb the initial assault of 100+ tritons long enough for mindbLasting. Getting a second water fortress might take some time.