> By definition a liquid cannot be below its freezing point until it has completed its phase change.

Supercooled water is a thing: (and I've seen it a few times myself)

https://en.wikipedia.org/wiki/Supercooling

Yes. My point was that it's easier(?) to get below freezing point above water than below. So while the cold air keeps the upper part of the iceberg (relatively) intact - it will slowly melt below the sea until the center of gravity changes enough to flip over.