past participle of do (v.); from Old English past participle gedon (a vestige of the prefix is in ado). As a word of acceptance of a deal or wager, 1590s. U.S. Southern use of done in phrases such as done gone is attested by 1827, according to OED: "a perfective auxiliary or with adverbial force in the sense 'already; completely.' "
Meaning "finished" is early 15c. To be done in "exhausted" is by 1917. Slang done for "doomed" is by 1803 (colloquial do for "ruin, damage" is from 1740). To have done it "to have been very foolish, made a mess of things" is from 1837.