[Agema]

Against Rlyeh, you don't need sea trolls, if you're attacked earlier.

You can send in a Basalt King or three with some form of priest. Bless them, and even just a modest N/S bless takes the sting off the torrent of mind blasts. The basalt kings are not really there to do anything but soak up the mind blasts, but they don't half save the rest of your army. Oh, and they cast Iron Will as well (if you're defending at least - chances are you'll get paralysed first when attacking). 40 mind blasts a turn will undoubtedly paralyse and start damaging your 20+ MR basalt kings rapidly, but you'll take pain sufficiently sparingly that even a gentle HP regeneration from N bless makes them unlikely to die.

You can give the basalt king amulets of MR, or even - think about it - lead shields. After all, who cares about taking massive fatigue from spellcasting and fighting when your basalt king is there to do neither?