No doubt about it, those knights are *tough* with a W/S bless, I'm going head to head with them as MA Atlantis in the Evermore game right now. The thing about Atlantis is their troops just plain suck, certainly nothing at all that will even make a decent speed bump to a big group of those knights. R'yleh isn't much better. You definitely have to work a lot harder (I wouldn't say its a fair fight against equal opponents), but with R'leh/Atlantis you should be focusing more on mages than troops...Oceana is both investing in expensive knights *and* the design points to double bless them. Then comes the trick of figuring out how to make your mage superiority effective underwater.
Since there are precious few damage dealing spells that work underwater you want to think more along the lines of buffs/debuffs as Meglobob alluded to mentioning destruction. Get some fairly tough summons (supported by chaff, of course) and then have a dozen mages casting body ethereal, luck, quickness, iron warriors, strength of giants, legions of steel, friendly currents, shark attack, school of sharks (great for soaking up that first strike bonus), and destruction. For example, as Atlantis I've been using Monster Fish (their national summon) to great effect when uber-buffed.