[turder]

Not just thousands, try tens of thousands.

For example, Australian Aborigines still have stories about the huge, man-eating lizards. It was considered just a standard myth until we discovered fossils of Megalania, a huge lizard matching the description, that went extinct soon after humans came to Australia.

Closer to the actual sea level rise topic, tribes of coastal northern Australia still have names and relatively precise description of land features (mountains etc) that are now underwater, but were land until 9k years ago.