[Firebreath]

There are several ways of going underwater.

Any leader with water magic can go under water (you can empower them, if you have gems).

There are lots of forged items which let a leader only go under water (e.g. amphibian suit of armour)

There are some some forged items which let a leader take a limited number of troops with him (these start at construction level 4, and you need water gems to make them).

There are lots of troops that you can recruit above ground that can go underwater naturally e.g. Shamblers, fishmen. I think that you don't even need to search for them, them come automatically. Undead can also go underwater (with a penalty). They're easy and cheap to raise, with only 1 point of death magic, even if they're not all that effective.

Some mercenaries have underwater troops.

You can make some underwater mutated troops (something to do with blood magic, which I don't know much about).