I did some research using the Corpus of Historical American English, and it paints the following picture:
(X axis: year, Y axis: incidences per million words)
This shows that from whence has been in constant use all the way back to 1810 (that's how far the Corpus goes). Indeed, as the World Wide Words post already linked by Shaun says:
And even a brief look at historical sources shows that from whence has been common since the thirteenth century. It has been used by Shakespeare, Defoe (in the opening of Robinson Crusoe: “He got a good estate by merchandise, and leaving off his trade, lived afterwards at York; from whence he had married my mother”), Smollett, Dickens (in A Christmas Carol: “He began to think that the source and secret of this ghostly light might be in the adjoining room, from whence, on further tracing it, it seemed to shine”), Dryden, Gibbon, Twain (in Innocents Abroad: “He traveled all around, till at last he came to the place from whence he started”), and Trollope, and it appears 27 times in the King James Bible (including Psalm 121: “I will lift up mine eyes unto the hills, from whence cometh my help”).
Emphasis added. (The King James Bible was completed in 1611).
As you can see from the above graph, from whence is on a steady decline; however, so is whence all on its own, so the graph isn't really that helpful. What we really want is the ratio:
The values on the Y axis in this graph tell you how many times more often whence was used without from rather than with. So, around 1920, whence all by itself was roughly 10 times more popular than from whence; nowadays, on average, every second usage of whence is prefixed by a from, according to the Corpus.
In other words, from whence has been actually gaining "relative" popularity since 1920.