The same was said about the Coelacanth (extinct with the dinosaurs) until scientists noticed they were fairly regularly showing up in fish markets around the Indian Ocean. Turns out they just live so deep that unless you're netting deep, you'd never know they were there.
Megalodon probably disappeared because there wasn't enough prey left for a shark that big -- but the Middle Ages were a time when sea monsters were considered more likely to be real than not, and understanding of ecology was very poor, evolution hadn't ever been considered, and the idea that the Earth might be more than a few thousand years old would be hush-hushed (or, if you shouted it loudly enough and started to convince others, might get you martyred).
A shark as big as as ship wouldn't have seemed out of place in that world view, especially to seafarers in the right oceans to have seen sperm whales (of similar size), or the still bigger blue whales. There doesn't need to be an explanation, under that time's world view, of why Megalodon is still around -- they just have a shark big enough to swallow a small rowboat whole, and that's the way the world is. There aren't many of them, at least not close to continents where people willingly sail -- but there aren't none, either.