Polymoph is a touch spell. If you can reach out and touch something, sure. As the target is underwater, you will need to have Freedom of Movement in order to attack it. Presumiably, this is because attacking from land into water is physicalLy impeded in a way that Freedom of Movement overcome.
SRD said:
Baleful Polymorph
Transmutation
Level: Drd 5, Sor/Wiz 5
Components: V, S
Casting Time: 1 standard action
Range: Close (25 ft. + 5 ft./2 levels)
Target: One creature
Duration: Permanent
Saving Throw: Fortitude negates, Will partial; see text
Spell Resistance: Yes
This was the "Polymorph" I was referring to, a "targeted" spell. Sorry I wasn't more clear. I was thinking of the kind you throw on an enemy in combat.
I guess the key is the difference between "cover" and "concealment". If you can have cover without concealment (and
Wall of Force pretty much says you can), then aimed and targeted spells would work. If the ruling is that the surface of the ocean isn't transparent like a shallow stream or fish pond, then you're back to trying to target a creature you can't see.
IRL, you can't see into ocean water, or even most freshwater bodies such as lakes, more than a few feet from the surface. I guess that's why, when the rules said "total cover", I thought "concealment" as part of the deal.
As for magical combat between underwater opponents is concerned, I think there's a rule for visibility under water...
SRD said:
Stealth and Detection Underwater: How far you can see underwater depends on the water’s clarity. As a guideline, creatures can see 4d8×10 feet if the water is clear, and 1d8×10 feet if it’s murky. Moving water is always murky, unless it’s in a particularly large, slow-moving river.
Unless the sea is incredibly calm, I'd tend to call it "moving water". So an average maximum visibility of 40 feet or so, but as much as 80 on a good day.
The Kraken can Ink Cloud for additional cover/concealment, and has 60 ft Blindsense, which makes the lack of visibility less of a problem for it.