According to its entry in the Tresor de la Langue Française, the infinitive aller comes from the Latin ambulare ("I travel, walk"), while conjugated forms like je vais and j'irai come from vado ("I walk, go") and eo (inf. ire, "I go"). The Reichenau Glosses (7th c., p. 16) list the hypothetical Vulgar Latin form *alare in several locations, so it seems that this substitution is quite old. I'm just a hobby philologist, though, so I'd second the /r/etymology recommendation!
You could try over at /r/etymology.