Wordorigins.org

This verb ultimately comes from the late-Latin *exlītigāre via the Old French esligier and the Anglo-Norman aligier, meaning to clear at law. One might think that it comes from the Latin allēgāre, which has the same meaning as the modern English word, but this similarity is due to later conflating the two terms. If it came from the latter root, the modern form would be alleague.

The original sense of allege was to make an oath. It appears in a manuscript titled Pearl, c.1325:

To corte quen þou schal com...Þer alle oure causeȝ schal be tryed, Alegge þe ryȝt.
(To court when you shall come...There all our cases shall be tried, Allege the right.)

The sense meaning to assert without proof, which is the sense most in use today, appears shortly after. From William Langland’s 1377 Piers Plowman (B text):

Þei wol allegen also, quod I, and by þe gospel preuen.
(They will allege also, say I, and by the gospel prove.)

(Source: Oxford English Dictionary, 2nd Edition)