[Taqwus]

For standard Ulm, use Earth magic to get a force which will go underwater. Mechanical Men and Living Statues are amphibious, and Gargoyles might be as well, and they have the additional advantage of being immune to poison (a lot of underwater types use poisoned gear...). You'll need to attach 'em to an amphibious commander, however (e.g. one with a breathing item).

Also, consider using Earth Attack to kill off triton commanders; 100 tritons, without commanders, will rout instantly instead of surrounding and attacking.