I am 99% sure the earliest reference is in John of Fordun's Chronica Gentis Scottorum, written in the second half of the 14th century. Fordun is the earliest historian to provide accounts of the long line of largely invented Scottish monarchs that were created as a counter-myth to the English mythological origin stories.
Fordun also created, or recorded for the first time, a legendary origin for the "Auld Alliance", which was something else that it was useful to have a much longer precedent for than actually existed. Associating Scotland with Charlemagne gave "evidence" of Scotland's longevity as an independent nation existing on an equal footing with the greatest kings and loyal to the Holy Roman Empire.
In fact the "Auld" Alliance wasn't very old at all when Fordun wrote, dating back no further than the reign of John Balliol and 1295, almost within living memory.
The importance of the newly-minted myth, however, can be seen from the fact that it was also incorporated into the official explanation of the Scottish Royal Standard. The red border pattern of alternating fleur-de-lis in the standard (called a "double tressure flory counterflory gules" in heraldry-speak) surrounding the red Scottish lion was claimed to be a gift of Charlemagne to the Scots reflecting the alliance and the relationship of Scotland with the (Frankish/French) Holy Roman Empire. In fact it is seen used as part of the standard only from the reign of Alexander III in the late 13th century, a few decades before the Franco-Scottish Alliance was first agreed.
Link to Fordun's chronicle (Skene translation). Account of Achay and the Franco-Scottish Alliance begins at page 127.
