Proto-Germanic *walχo-z "foreigner" shows up in Old English wealh "Celt, Briton", Old Norse Valir "Gauls", French Wallon. It was borrowed into Slavic, for instance Czech vlach, apparently meaning "Italian". The Anglo-French Waleis shows up in the name Wallace. With the adjectival -ish suffix, *walho-z became English Welisc, then Welsh.
Old English walhhnutu is wealh plus hnutu "nut". Etymologically it "meant the nut of the Roman lands (Gaul and Italy) as distinguished from the native hazel" according to the OED.
According to Skeats, wealh in the plural was wealas "foreigners", which became Wales.