"gone, gone by; gone away," early 14c., a shortened form of agon "departed, passed away," past participle of a now-obsolete verb ago, agon "to go, proceed, go forth, pass away, come to an end," from Old English agan. This was formed from a- (1) "away" (perhaps here used as an intensive prefix) + gan "to go" (see go (v.)).
As an adverb, "in past times" (as in long ago) from late 14c. The form agone is now obsolete except as a dialectal variant.