According to Wiktionary (a source I should perhaps have checked before asking), the all- forms ultimately derive from
Vulgar Latin alare (attested in the 7th century Reichenau Glosses). This has traditionally been explained as deriving from Latin ambulare via or together with ambler (compare Old Provençal amblar, Italian ambiare, Romanian umbla), but this explanation is phonologically problematic. Several theories have been put forth since the 17th century to explain how ambulare could have become aller.[1] Since at least the 18th century, some have suggested that aller derives not from Latin but from Celtic[2], Gaulish *aliu: compare Welsh elen (“I was going”), Cornish ellev (“I may go”), and also Franco-Provençal alâ, allar and Friulan lâ (“to go”) (compare lin (“we go”), lât (“gone”)).
Latin vādō (“go”) supplies the present tense forms and īre, present active infinitive of eō, supplies the future and conditional.
As was explained to me by @Sindry, this type of mixed etymology is called suppletion, instances of which are overwhelmingly restricted to the most commonly used lexical items in a language.