Hm, very difficult to have them 'dominate' Europe, but much more than OTL is possible. Eg at the same time that Britons were migrating to Brittany - 5th and early 6th centuries, there was a parallel, but very much smaller migration to Galicia in the Iberian peninsula. We know very little about this; it appears to have had few longterm consequences. Now, supposing the main focus of Brythonic migration was Galicia and not Brittany. They are welcomed by the not very numerous local population, defeat the Suebi, and immigration is so overwhelming that by 600 CE Brythonic is the dominant speech throughout Galicia. The kingdom(s) they found there holds off the Visigoths. The Islamic invasion still happens much as in OTL, and as in OTL Galicia is mostly spared, and rapidly regains its independance. At this time the language is consolidated, and, because it's all one realm, even spreads into Asturias to some extent.
The Brytho-Galician kingdom takes part in the Reconquista, and the language naturally spreads south into the reclaimed lans of Lusitania, ie Portugal. Subsequent history runs parallel to ours; Lusitania remains independant of Spain, develops a maritime empire, and colonises half of South America. The language, though influenced by Iberian Romance, remains strongly Celtic. I envisage it as being a bit like the Vannes dialect of Breton. Even when the king is from a foreign dynasty, the aristocracy remains firmly Brythonic in speech and culture, and patronises poetry in the traditional Celtic manner.
Voila! Portugal, Galicia, Brazil, and Western Asturias all Celtic speaking!