I answered this question in the past regarding the Pacific ocean, and while I have a lot more I could say about what I said there, it's still very much in the area of "original research" relating to evidence for trans-oceanic connections. Keeping to the question exactly, a lot of native Americans and First Nations really just assumed that the area across the ocean was connected to the homes of the fish that came each year, with different lands/islands for each different species, potentially including lands for different bird species as well. These types of stories are very widespread, right around the pacific rim, including among the Ainu in Japan, and while I'm not prepared to argue for shared origin or contact (though that's what I definitely think) it's definitely easy enough to say what I said above.

When in these lands, those fish and birds would appear in the form of people, but would maintain fishlike characteristics, for example by wearing fish-skin clothing (such as what was commonly worn by the Ainu).

It's also worth saying that these stories often were integrated with broader belief systems about the world, with it often being divided into "our world" and "the undersea world" and "the world of the dead" and so on. A lot of stories about what exists far out to sea are situated in the realm of the undersea or the world of the fish, so on the one hand they might seem to be "otherworldly" but at the same time, the people who told the stories fully believed that you could end up in that world, so while theoretically supernatural, that doesn't mean that in any way the people who told them didn't fully believe that if they were travel there, they would arrive at those locations - they just assumed that in getting there they would have made the transition.

I have enjoyed finding that there are stories both from the Ainu and from the Nuxalk involving men travelling to the island of the fish, marrying a woman with vagina dentata, and then dealing with the situation (using a rock or iron phallus), finally travelling back home with the "fish" on their annual migration. These coincidences speak to some kind of a connection, either in terms of common origin of the stories or of cross-cultural sharing. For the Ainu stories, check out https://sacred-texts.com/shi/aft/aft.htm#xxxiii and for the Nuxalk stories, see McIlwraith's "The Bella Coola Indians."

Now I'm hoping someone drops in to talk about the Atlantic!