Here is what I was able to find doing a quick online search.
This gives Galahad as being 'Gwalchavad' in Middle Welsh.
http://en.wikipedia.org/wiki/Galahad
This website says that his "name may be of Welsh origin or come from the place name Gilead in Palestine."
http://www.kingarthursknights.com/knights/galahad.asp
If you scroll down to the entry from the Oxford Dictionary of Celtic Mythology, it says "Although Galahad does not have an obvious parallel in Celtic literatures, enthusiasts have posited a Welsh etymology for his name: gwalch [hawk, falcon, crested one]; cad [battle]."
http://www.answers.com/topic/galahad-religion-in-encyclopedia
As for Galehaut, which is also spelled Gallehault, I found even less. His name is 'Galeotto' in Italian. 'haut' in French simply means 'high', and I found that 'hault' is the Old French spelling of 'haut' and an archaic meaning was 'haughty'.
http://en.wiktionary.org/wiki/hault
Gal- seems to be often thought of as a prefix coming from Welsh and Breton names, such as with Galahad and Gawain. It's possible his name is a blending of Celtic and French (since Arthurian stories came to be so influenced by the French and French storytelling, etc). Or it may have had a Celtic root that was given a French ending to signify something about the character. All of this is my own conjecture.
Interestingly, I found that the French name for Wales is 'Galles'. It likely comes from the same name as the Gauls, the Celtic people who inhabited France long ago and lent their name to it as a place. Native French people/things can still be referred to as 'Gallic'.
There is this conversation thread from someone asking the same question as you:
https://groups.google.com/forum/#!topic/alt.legend.king-arthur/5l6kzjNcfbU
A little ways down, one person provides a list of different variations in the spelling of Galehaut's name throughout historical Arthurian literature. Perhaps some of those would prove to be leads to its origin.
Hope this is helpful! :)