[Amhazair]

It also depends a lot on the stage of the game of course. From your first post I'm guessing it's still early in the game?

In any case, you'll need a decent water income to be able to effectively bring the fight to R'lyeh in the sea. As Twan said, you can use your Skrattis as thugs to conquer lightly defended provinces. If you've taken a bless the giant priests make for good thugs too. As you're facing R'lyeh, make sure to boost their MR. You have the advantage that you have excellent W/D mages, allmost all of whose useful spells will still be available under water. But you'll obviously need to provide the necessary water breathing equipment.

You might want to try to raise a big ruckus in the game thread, about how you're fighting the good fight against the huge threat of LA R'lyeh, and how they will become unstopable if left alone. You might find someone willing to help you out by donating some water gems to the cause. Or if you're lucky even an ally.

Ultimately, you are obviously at a disadvantage when entering the seas. If you're not noticeably stronger than him (or the greatest military genius since Gengis Khan) you might have to settle for whipping his *** whenever he comes out of the water, and raid some lightly defended water provinces to annoy him when you have the opportunity.