Valhǫll in Old Norse comes from valr and hǫll -- literally "hall of dead warriors". Hǫll is reconstructed in Proto-Germanic as hallō, itself from the Proto-Indo-European root ḱel, meaning "to cover".
Consider the Norse Hel (both the underworld and the name of the deity ruling over it). Compare with Old English hell, from Proto-Germanic haljō, from Proto-Indo-European ḱelnó, "room", in turn from the root ḱel -- "to cover".