The legend of the kraken (and other sea monsters too) are believed to have originated from sightings of the giant squid. You have to remember that they’re incredibly rarely seen even today, and until they were properly documented the average person would find the concept of a squid that large ridiculous.
Imagine a fisherman spotting the carcass of an enormous tentacled beast in the water, then going home and telling everyone about what he saw. One long game of telephone and a couple more sightings later, you have the kraken.