c. 1300, from Old French essillier "exile, banish, expel, drive off" (12c.), from Late Latin exilare/exsilare, from Latin exilium/exsilium "banishment, exile; place of exile," from exul "banished person," from ex "away" (see ex-); according to Watkins the second element is from PIE root *al- (2) "to wander" (source also of Greek alaomai "to wander, stray, or roam about"). De Vaan expands on this:
Several etymologies are possible. It might be a derivative of a verb *ex-sulere 'to take out' to the root *selh- 'to take', cf. consul and consulere; hence exsul 'the one who is taken out'. It might belong to amb-ulare < *-al- 'to walk', hence 'who walks out'. It might even belong to *helh-, the root of [Greek elauno] 'to drive': ex-ul 'who is driven out' ["Etymological Dictionary of Latin and the other Italic Languages"]
In ancient times folk etymology derived the second element from Latin solum "soil." Related: Exiled; exiling.