The Fiddler's Companion goes into some detail on the subject of the tune, but spreads the matter over several separate entries which contain various inaccuracies, misunderstandings and contradictions, beside failing to identify sources for some of the commentary. It is therefore quite misleading and I will not quote from it here, though I will address some of the points it raises.

Burns himself identified the source of the melody as he knew it, in a letter to George Thomson (November 1794):

'There is an air, "The Caledonian Hunt's delight", to which I wrote a song that you will find in Johnson [Scots Musical Museum, IV, 1792, no 374]. "Ye banks and braes o' bonnie Doon"; this air, I think, might find a place among your hundred, as Lear says of his knights. Do you know the history of the air? It is curious enough. A good many years ago, Mr. James Miller, writer in your good town [Edinburgh], a gentleman whom possibly you know, was in company with our friend [Stephen] Clarke; and talking of Scottish music, Miller expressed an ardent ambition to be able to compose a Scots air. Mr. Clarke, partly by way of joke, told him to keep to the black keys of the harpsichord, and preserve some kind of rhythm, and he would infallibly compose a Scots air. Certain it is, that in a few days, Mr. Miller produced the rudiments of an air, which Mr. Clarke, with some touches and corrections, fashioned into the tune in question. Ritson, you know, has the same story of the "Black keys;" but this account which I have just given you, Mr. Clarke informed me of several years ago.

Now, to shew you how difficult it is to trace the origin of our airs, I have heard it repeatedly asserted that this was an Irish air nay, I met with an Irish gentleman who affirmed he had heard it in Ireland among the old women; while, on the other hand, a countess informed me, that the first person who introduced the air into this country was a baronet's lady of her acquaintance, who took down the notes from an itinerant piper in the Isle of Man. How difficult then to ascertain the truth respecting our poesy and music! I, myself, have lately seen a couple of ballads sung through the streets of Dumfries, with my name at the head of them as the author, though it was the first time I had ever seen them.'

The Letters of Robert Burns: Selected and Arranged, with an Introduction,
by J. Logie Robertson, M.A. The Thomson letters, XX.

Thomson was the editor of The Select Melodies of Scotland, Interspersed with those of Ireland and Wales, 6 vol, 1798-1841. Stephen Clarke, organist at the Episcopalian Chapel in Edinburgh, was the musical editor of SMM. He was actually English, born in Durham.

SMM credits 'Mr James Millar, Writer in Edin^r.' with the tune for 'Ye Banks and Braes'. 'Writer' here seems to be short for 'Writer to the Signet'; that is, a lawyer. It had been printed a few years earlier by Niel Gow in his Second Collection of Strathspey Reels (1788) as 'The Caledonian Hunt's Delight - a favourite air'; the book was dedicated to the Caledonian Hunt, and it has been suggested that it was Gow who named the tune. Burns had already written a song set to it, 'Caledonia', in 1789: see Burns Monument Trust: MS

'Caledonian Hunt's Delight' appeared in Aird's Selection of Scotch, English, Irish and Foreign Air's (IV, 1796) subtitled 'Irish', repeating the rumour referred to by Burns. That attribution is also repeated elsewhere, but no evidence, so far as I can tell, has ever been adduced to support it; though O'Neill, misunderstanding a comment made by George Farquhar Graham (see below) claimed that was some basis for it. More recently, The Oxford Companion to Music has implied that Frank Kidson thought it Irish: that appears also to be a misunderstanding of what Kidson actually said.

An interesting question was raised by William Chappell (Popular Music of the Olden Time, II, 1859, 794-5): noting that an essentially identical melody appeared in Dales' Collection of English Songs published some time after 1880, set to the song 'Lost, lost, lost is my quiet', he concluded that the melody was originally English, and that Clarke had merely made a few small alterations to it; Burns' anecdote being a fiction. Chappell printed the music, as follows:

X:1
T:Lost, Lost is My Quiet
B:Chappell, Popular Music of the Olden Time, II 794-5
N:taken from Dale's Collection of English Songs, i, 157, nd
L:1/8
Q:1/8=100
M:3/8
K:G
"Plaintively" G2 z|A2 z|B3/2d/B|A3/2G/A|B3/2A/G|GED|
w:Lost, lost, lost is my qui-et, for e-ver, since Hen-ry has
DGB|(B2 A)|G2 z|A2 z|B3/2d/B|A3/2G/A|B3/2A/G|
w:left me to mourn,_ To for-get him how vain my en-dea-vour, a-
GED|DEG|G3||(d2 e)|dBG|"Sym." D2E|
w:las! will he ne-ver re-turn? Ah!_ well-a-day!
DB,G,|dBG|"Sym." DB,G,|e2d/c/|(B A2)|G2 z|A2 z|
w:*** well-a-day! *** Ah! well-a-day!_ Lost, lost,
B3/2d/B|A3/2G/A|B3/2A/G|GED|DEG|G3|]
w:lost is my qui-et, for e-ver, since Hen-ry has left me to mourn.

Chappell's assertion went unchallenged for some time. George Farquhar Graham (The Songs of Scotland, adapted to their Appropriate Melodies, edition of 1888, 300-301) makes the same point, quoting in support of it Burns's fragment 'Why, why tell thy lover', also set to the CHD tune, with his comment 'Such is the peculiarity of the rhythm of this air, that I find it impossible to make another stanza to suit it.' FG went so far as to print the tune as quoted by Chappell, with Burns' words set to it, in order to show how the words better fitted the different phrasing. They do fit far better than they do to the tune as used for 'Bonny Doon'; unfortunately for the argument, Burns wrote them in 1795-6, well after his two previous songs set to the melody. Perhaps Thomson had sent him the English form; or perhaps Burns was confused. He was near the end of his life, and suffering from toothache at the time.

Farquhar Graham further wrote: 'As early as 1690 we find in Playford's Apollo's Banquet "a new Tune", which in its first part bears so striking a resemblance to our modern air, that it is just possible it may have given rise to a statement alluded to by Burns...' He goes on to quote Burns' comments on alleged Irish and Manx provenances and on the general difficulty of establishing the truth in such cases (quoted above), concluding: 'We may remark, is it possible or probable that Playford's "New Tune" can have spread so widely over the British Isles as to be claimed by each nationality as its own? or is the melody so obvious as to suggest itself to many individuals acting independently of each other?'

Unfortunately I've only seen the 1888 edition of the book, which appeared in several forms from c.1854; so I can't be sure whether or not that information appeared in editions prior to PMOT, and whether FG's comments derived from Chappell, or vice versa, or whether they arrived independently at the same conclusion. At all events, Chappell does not mention Apollo's Banquet in his note; and, since there are four tunes called 'a New Tune' in the 1690 edition (and four called 'a New Scotch Tune', come to that), that avenue can't be explored further until we know what all those tunes actually were.   

'The Fiddler's Companion' cites John Glen, without providing any reference (the only work of his in their bibliography is The Glen Collection of Scottish Dance Music, Edinburgh, 1891/5; but Bruce Olson refers to Glen's Early Scottish Melodies, 1900, 55, which will be the correct citation) and his apparent claim that the 'new tune' in Apollo's Banquet referred to by FG was called 'a Scotch Tune'. The number quoted is 68, which is wrong; though this may be a misprint for B8, one of the 'New Scotch Tunes'. Perhaps the compiler of FC hasn't actually seen Glen's book (as I also have not) and relies here -as he often does- on an unchecked and inaccurate third-party report.

In an article in The Leeds Mercury in 1890/1, Frank Kidson challenged Chappell's conclusions, pointing out that internal evidence put the publication of Dale's Collection of English Songs at no earlier than 1798. Where Dale got the tune is not explained, but it had certainly been published in Scotland (albeit in a different form) some 10 years earlier. 'Lost, lost, lost is my quiet', incidentally, should not be confused with 'Lost is my quiet for ever', which, as Kidson pointed out, appeared in Orpheus Britannicus (1701) set by Purcell to an unrelated melody.

That's about it for now. I might add, in conclusion, that James C Dick, The Songs of Robert Burns (1903) wrote: 'Two bathetic stanzas, written by a music publisher, were added to the song, and printed in the Rocket Encyclopedia, Glasgow, 1816, i. sg.' These are likely the two involving 'Luman', quoted earlier from a Gateshead broadside edition.