There is also a possible link with the Viking 'Val' - an election place (I think). Not so much a place of voting, but of 'choosing'. But this is a slim possibility.
A further thought closer to home- my local hillfort is Wallbury. This combines the enigmatic wall element with the burh. Massive ditch and ramparts here so the wall could be the ramparts. Earliest recorded name according to Essex volume of EPN Soc is Walla -1086 Domesday. Not sure this helps much.