Old English eall "every, entire, the whole quantity of" (adj.), "fully, wholly, entirely" (adv.), from Proto-Germanic *alnaz (source also of Old Frisian, Old High German al; German all, alle; Old Norse allr; Gothic alls), with no certain connection outside Germanic. As a noun, in Old English, "all that is, everything."
Combinations with all meaning "wholly, without limit" were common in Old English (such as eall-halig "all-holy," eall-mihtig "all-mighty") and the method continued to form new compound words throughout the history of English. Middle English had al-wher "wherever; whenever" (early 14c.); al-soon "as soon as possible," al-what (c. 1300) "all sorts of things, whatever."
Of the common modern phrases with it, at all "in any way" is from mid-14c., and all "and everything (else)" is from 1530s, all but "everything short of" is from 1590s. First record of all out "to one's full powers" is 1880. All clear as a signal of "no danger" is recorded from 1902. All right, indicative of assent or approval, is attested by 1837; the meaning "satisfactory, acceptable" is by 1939, from the notion of "turning out well."
The use of a, a' as an abbreviation of all (as in Burns' "A Man's a Man for A' that") is a modern Scottishism but has history in English to 13c.