Intriguely, Columbus claimed that in 1477, after visiting Bristol, England (which is confirmed), he visited Iceland, where the stories of Markland would have predominated.
"In May 1476, [Columbus] took part in an armed convoy sent by Genoa to carry valuable cargo to northern Europe. He probably docked in Bristol, England, and Galway, Ireland. He may have also gone to Iceland in 1477. It is known that in the autumn of 1477, he sailed on a Portuguese ship from Galway to Lisbon, where he found his brother Bartolomeo..."
A major backer of their voyages was Welshman Richard ap Meryk, sometimes elided to Ameryk. There's a theory that the fishermen established a processing station in Newfoundland and called it Ameryka in his honour, associating the left-hand side of the pond with that name in voyagers and cartographers minds.
I thought it was well established that the name America came either directly or indirectly from explorer Amerigo Vespucci.