On Earth
Depends entirely on the beast in question.
Blue whales are the largest mammals, and they develop quite severe spinal issues in their old age - even having water support their bulk, their skeletal system still takes a beating. Clearly a mammal can't get much bigger (not with a standard bone structure and composition), even in the oceans.
An animal that doesn't have bones, however, might grow to be quite a bit larger.
The problem becomes, as you've mentioned, how would that creature eat enough to sustain itself. The problem only grows as you envision a population of hundreds of such monsters.
Whales solve the problem by ingesting a large amount of water and then spitting it back out, filtering small creatures out in the teeth and then swallowing them.
Squids on the other hand, capture their prey and eat it the good ol' fashioned way. So a kraken (aka a giant squid) would probably go after proportionately large prey, such as a blue whale. There's not that many blue whales to go around though, nor really whales of any other kind.
Fish would be too tiny for the kraken to even bother with, at which point it's probably targeting sea fearing vessels and snatching people off the decks - another time honored kraken tradition.
I think this is the reason why so often in fiction these gigantic animals are one of a kind - the results of experiments, or mutation triggered by some other-worldly event (radiation from a meteor, etc).
Alien World
Imagine a planet with lower gravity than earth, or on which creatures have developed on different principles than on Earth (aka skeletal structure and composition, etc.).
It would make total sense for mega-sized species to develop if they don't face the "structural" issues that Earth bound creatures do. (In Avatar, for example, the size of the local species is explained by them having carbon nano-tube naturally occur in their bones - it's basically hand-waving the size issue aside).
At that point you're making up your own rules though.