Magnus and the Mountains
Most of the stories start as tales of their own Monthjumps, with many like yours, but you hear of one man who as he dove, saw a kraken surfacing.
"Luckily, he thought of me as too small a bite for him, and e'en more, that he didna seize on the ship, which was the Marie of Yonder Island." This brings up talk of good ships, unlucky ships, and harsh masters, and fair and generous captains.
There is talk of pirates, and of kraken and sea snakes, and the Mages of the Ancient Times who could do most anything, and that brings up the Mage of the Southern Seas which the men swear has a mobile island hidden in the fogs.
"He's the last of his kind, not elf, not dwarf, not Man, nor catfolk, nor orc, nor troll. He can call up a typhoon by snapping his fingers, and ride the lightning. But I've never seen him, few do these days."