From public records:--
Andrew Achnachie of Achnachie {Of That Ilk] in the year 1555 granted a charter of his lands of Achnachie to Thomas Gordon of Bannaketill.

Andrew Achnachie of Achnachie [note he still kept his territorial designation after he had disponned his lands of that name to T.G.] granted a ratification of this charter to James Gordon as heir to his brother Thomas in the year 1569.

It is easy to see that for a time after the change of ownership of these lands folk would refer to the new owners as Achnachie Gordon in order to differenciate them from the Achnachies of Achnachie [they still holding to their territorial designation as shown by the 1569 charter]

A John Gordon of Achnachie appears in the Aberdeen records in 1601.

There are at least six spellings of Achnachie in the various charters, sometimes two or three in the same charter.

The above settles the point regarding the name Achnachie Gordon and in my opinion gives a period for when the ballad was composed ie.late 16th./early 17th C. in the period when folk still remembered the old owners of the lands by adding Gordon to the territorial designation.
This, of course, gives no clue to the identity of Jeannie Gordon but it can safely be taken that she was no tocherless lass as the offer by her father to mend the mairrage wi ten thoosan croon testifies.
My research into her identity is ongoing.