Where did the term "doggone it" come from?

From Etymonline:

doggone 1851, Amer.Eng., a "fantastic perversion of god-damned" [Weekley]. But Mencken favors the theory that it is "a blend form of dog on it; in fact it is still often used with it following. It is thus a brother to the old English phrase, 'a pox upon it,' but is considerably more decorous."

Others have it derived from the Scottish dagone, or "gone to the dogs," but there's a bit of debate about that.

From my own search, I found several pre-1851 uses. It looks like it may have first appeared in print in a British publication, albeit of an American vernacular dialog, in Adventures in Mexico and the Rocky Mountains by British explorer George Ruxton, 1847 (date check):

It subsequently appeard three times in 1848 in Blackwood's Edinburgh Magazine, in articles written by Ruxton while living in America.

One possible route to doggone would be God damn -> God darn -> doggarn -> doggone. The earliest I could find a reference to dog garn is in the play Ossawattomie Brown, or The Insurrection at Harper's Ferry, by Mrs. J. C. Swayze (1859) reprinted here. There are also a few Google books hit for doggarn in the 1870's and 1880's. I think this is fairly good evidence for the derivation through doggarn.