First, megabeasts are basically always creatures actually of myth, so a magalodon isn't really a candidate for megabeast for the same reason that T-Rex isn't. Part of the point of the megabeasts, and the names of the ages, is that the world as a whole is more mythic when they are around. Non-mythical creatures as megabeasts kind of go counter to that notion. (Krakens would be fine by that standard, though... As would something like Scylla and Charybdis as some sort of semi-megabeast that just fills up a specific "lair".)
In order for sea beasts to be any real threat, however, they need to be amphibious.
Krakens from classic myth were generally attacking ships, since those were things they could actually, you know, reach.
And reach is kind of a big deal, since you currently can't reach, even if you're a dragon or bronze colossus or some other creature that hypothetically should be able to reach at least more than one tile away. (Barring dragonfire, of course...) Having a Kraken show up at a fortress, even one near an ocean, will likely just involve one menacingly glaring at your fort from the water's edge before likely getting swept up in a wave and getting beached and air-drowning... which isn't exactly a climactic showdown.
You also can't really send any dwarves out to fight it, being as dwarves already infamously lose fights against significantly less dangerous carp by simple virtue of the fact that they often can't swim. (They also lose fights against the urge to go walking off a @#*$ing waterfall, so putting dwarves anywhere in the path of water is generally inadvisable.)
Basically, the reason you don't have krakens to fight right now is that there's no actual way for a normal dwarven fortress to have a fight with one.
I'm sure krakens and sea serpents are prime suspects for grand adventure when we get seafaring adventures into the game, but until boats are in, I doubt we'll actually see strictly aquatic megabeasts.
Something more like Godzilla walking up off the ocean floor, but capable of living on and stomping flat the land would be a more plausible threat to most forts.