A related phrase: 'draw the long bow'
As a supplement to JEL's answer, I offer this information on a related expression: draw the long bow. Eric Partridge, A Dictionary of Slang and Unconventional English, second edition (1938) has this entry for draw the long bow:
bow, draw the long, To exaggerate ; lie. From ca. 1820 ; coll[oquialism]. Byron."
A Google Books search yields several other reference woks that discuss this expression. From Ebenezer Brewer, Errors of Speech and of Spelling, volume 1 (1877):
To draw the long-bow, greatly to exaggerate one's own prowess or achievements.
From Eliezar Edwards, Words, Facts, and Phrases; A Dictionary of Curious, Quaint, and Out-of-the-Way Matters (1882):
Long-bow. The long-bow was a powerful bow used by soldiers before the introduction of gunpowder. 'To draw the long-bow' was formerly a term applied when one boasted of his skill or strength as an archer, not always truthfully, but as a vain-glorious soldier might after the wars. It is now applied, in general terms, to notorious liars, who are said to 'draw the long-bow.'
Brewer returned to the subject in Dictionary of Phrase and Fable: Giving the Derivation, Source, or Origin of Common Phrases, Allusions, and Words That have a Tale to Tell (1900):
Longbow. To draw the longbow. To exaggerate. The force of an arrow in the longbow depends on the strength of the arm that draws it, so the force of a statement depends on the force of the speaker's imagination. ...
And from Thomas Davidson, Chambers's Twentieth Century Dictionary of the English Language (1907), which has entries for the phrase under both Bow and Long:
To draw the long bow, to make extravagant statements ;
...
Draw the long-bow, to exaggerate, to tell incredible stories ;
An early instance of the expression used to mean "exaggerate" appears in "A Stipendiary Romish Priesthood," in Dublin University Magazine (December 1834):
The simple truth we have long known ; but the simple truth appeared so like extravagant falsehood, that, coming from a Protestant witness, it must needs have passed for one of those party exaggerations which could only do discredit to those by whom it had been disseminated or believed. "Come," our English friends would say, "this is really too bad. O'Connell and his tail may draw the long bow a little in describing their priests as the most excellent and exemplary beings upon the face of the earth, but you, surely, do them less than justice in thus confounding them with publicans and and sinners."
And here from Canto XVI of Don Juan is the instance from Byron that Partridge alludes to in his 1938 slang dictionary:
The antique Persians taught three useful things,
To draw the bow, to ride, and speak the truth.
This was the mode of Cyrus, best of kings—
A mode adopted since by modern youth.
Bows have they, generally with two strings;
Horses they ride without remorse or ruth;
At speaking truth perhaps they are less clever,
But draw the long-bow better now than ever.
Instances of 'stretch the long bow' from Australia
As I noted above in a comment to the poster, Australian newspapers between the 1860s and the 1930s record a number of instances of "stretch the long bow" in the sense of "exaggerate." Here are some examples drawn from the National Library of Australia's Trove newspaper database.
From "Snipe Shooting: A Good Day's Sport Indeed" the [Melbourne, Victoria] Australasian (October 24, 1868):
Sir,—Seeing in the Hamilton newspaper an account, of three days' snipe shooting, during which 134 brace of birds were killed by three guns, spoken of as being something extraordinary, induces me to send you the particulars of one day's shooting by three guns on Thursday, the 8th ultimo, when ninety-seven brace of birds were bagged. This, by some persons, may be considered only a stretch of the long bow. However, to proceed, I will give you the plain facts by stating that on the day named, guns being in order, ammunition provided, and horses in the trap, myself and two old friends had nothing to do at three p.m. but "jump into the waggon and all take a ride" to the trysting-place, about thirty miles away, which we reached in safety.
From "Meteorological Periodicity and the Present Drought," in the Brisbane [Queensland] Courier (September 12, 1877):
As it is my intention to give some account of his [the government astronomer for New South Wales, H.C. Russell's] labors in connection with this work shortly, I merely state here, en passant, that a perusal of its pages will be fraught with the greatest interest, and the student will learn from it a mass of facts concerning droughts, floods, storms, hail, snow, blight, visitations of caterpillars, and other singular phenomena, of which few have formed any conception. It would, doubtless, be considered a deliberate stretch of the long bow if I were to state that, in New South Wales cattle have been lost in snow storms; that at Kiandra the thermometer falls 8° below zero; that in 1867 a flock of 1500 sheep were killed by mosquitoes on a station near Rockhampton, that the first mosquitoes which appeared in Sydney made their triumphal entry in 1824, driving out swarms of blow flies; that in 1729 and 1828 smallpox decimated the blacks, and so on.
From "Rival Windiness," in the [Hobart, Tasmania] Mercury (October 28, 1889):
Thus comments a Wellington contemporary : — "After all Wellington is bearable, and the Auckland papers, in their wildest flight of abuse of the Empire City, never succeeded in equalling tho following:—The Lyttelton Times says that an idea of the fierceness of the recent nor'-wester 'can be formed from the fact that a woman, living near Mount Somers, after escaping from a falling house, had to sit on her children to prevent their being blown away. This may appear a stretch of the long bow, but to people acquainted with the locality it does not seem improbable."
From "Celestial Bowling," in the Bundaberg [Queensland] Mail and Burnett Advertiser (May 7, 1910):
As two well-known exponents of the game upon whoso greens, England's battles with the Spanlnrds were won (that is no longer stretch of the bow than the "playing fields of Eton" apocryphal remark) were practising with jacks and skips and things on the Bowling Club's territory yesterday afternoon, after an electric storm, when a solitary hailstone had a shot at the Jack.
From "Queensland Is Here!" in the [Sydney, New South Wales] Truth (January 24, 1937):
"Queensland is here" may be a stretch of the long bow, but the contingent that arrived in Sydney yesterday morning from Brisbane must have left that city—or at least the sailing section of It—rather bare.
And from "Symbolism Is Out, Policy Detail In," in the Canberra Times (March 10, 1989):
The same question should be considered now. Is the autocratic style of Malcolm Fraser comparable with the quasi-populism of John Howard? It would seem a long stretch of the bow. For better or worse, the differences between the conservative parties under Mr Howard and under Mr Fraser are at least as great as the differences in the ALP under Mr Hawke and under Mr Whitlam.
These examples should suffice to demonstrate longstanding use of "draw the long bow" in Australia between 1868 and 1937 to mean "exaggerate." In assembling these instances, I did not attempt to find similar instances that replace stretch with stretches/stretched/stretching, but I would be surprised if there were not a fair number of examples of those forms of the expression as well.
Likewise, I did not search for examples in English newspaper archives—though it seems likely that slang or idiomatic use of "draw the long bow" originated in England and that extension of the idiom from draw to stretch may have occurred there before it moved on to Australia. Certainly the 1869 Notes & Queries letter cited in JEL's answer, alluding to "a stretch of the long bow" suggests that both forms of the expression were known in England by the time the Trove database's first reported instance of it from Australia was recorded.