How does one fight the sea?

[Lazy_Perfectionist]

You may be able to blight their production provinces- given the common nature of amphib indies, not the best strategy. But keep in mind that the only place they can get mages underwater is from forts or magic sites.

Putting aside the fact that R'lyeh doesn't have capital only units, you can often gain quite a few advantages by causing tons of unrest in an enemy capital, the least of which is decreasing their gold income.