Benjamin of Tudela mentioned that in a search for the origin of this story, he came "across this very same question, posed to J. David Markham - President of the International Napoleonic Society . . . The noted historian of Napoleon answered that he had never heard that story. You can draw your own conclusions."
While there are many reasons why the story is probably only a story, it is a story, and the question is how old is it? And are there variations? To me it's a pity that the president of the International Napoleonic Society should have never even heard of the story, since I would think that the folklore and legends surrounding Napoleon should be of interest and known to him. And this is definitely a piece of Napoleon folklore.
Benjamin cited a book from 1954 which has the story, but has Napoleon not really getting it at all. In this version Napoleon is skeptical that mourning and lamenting will accomplish anything, but the author writes that he was mistaken - those who mourn the destruction will see it rebuilt.
In 1946 the YIVO Annual (Vol. 1) printed an English excerpt from the 1942 book Yidn in Frankraykh by Shmuel Zanvil Pipe called Napoleon in Jewish Folklore. The article contains 43 pieces of Napoleon folklore collected from "correspondents from all parts of Poland, as well as several from Palestine and one from Bagdad, Irak." It gives two versions of the Napoleon legend. The first is as I described, and the second is an elaboration of the 1954 version mentioned by Benjamin. In this version, Napoleon visits a synagogue in Vilna and cannot understand what wailing will accomplish. Seeing the lamentation, which he considers aimless, Napoleon points to his own sword and says "This is how to redeem Palestine."
Getting a little earlier - this article in the American Jewish Yearbook 26 (1924) pg. 306, translates a Yiddish article from January 1912 in a periodical called Warheit, and includes the legend - the version where Napoleon tells them that they will not regain the land by lamentation, but by force. This Yiddish article is all about how Jewish boys should join the Boy Scouts, mind you.
It existed in the 40s, it existed in 1912. Obviously the story was around. We cannot be sure of how old it is, and one version seems possibly to have been compromised by Zionist sentiment. To be sure, we cannot say if the Zionist version is the original, and the other version a pious retelling of that, or if the opposite is the case.
The earliest I have been able to find it in print is as an aside in an article on the Corfu esrogim controversy, in Hamaggid October 29, 1891:
In fact it is such an aside that the author of this piece doesn't even mention the contents of the story, only that he recalled Napoleon's words on Tisha B'av. On the one hand this is good. To be so flippant shows that it was perfectly well known in 1891, a cliche to the point that it only needed to be alluded to. On the other hand, we are unsure what Napoleon's words were, although if I had to guess from the context it is the version where Napoleon advocates force rather than passivity.
The Corfu esrogim controversy in this context refers not to the grafting issue, or high prices, but to the 1891 blood libel, which raised the issue of economically supporting antisemites.
In any case, the point seems to be that some version of this legend must have existed for some time, perhaps decades, before 1891. If an earlier source in print should turn up, I'll keep you posted.