The mere fact that a song is found in tradition in Newfoundland is not in itself any indication of its previous source, and the major collections of Newfoundland folk song include material of Irish, Scottish and English origins; with some French, too, as is to be expected given that the place was settled from all those countries; besides plenty of "home grown" songs.

An early form of Loch Lomond appeared on broadsides around 1840 as Flora's Lament for her Charlie; examples can be seen at Bodleian Library Broadside Ballads:

Flora's lament for her Charlie [W. & T. Fordyce, Printers, 15, Grey St., Newcastle: Harding B 11(4363) Between 1832 and 1842]

and at Glasgow Broadside Ballads: the Murray Collection:

Flora's Lament For Her Charlie [Robt. M'Intosh, 96 King Street, Calton: Mu23-y3:013. No date.]

One verse is particularly worth quoting:

It's not for the hardships that I must endure,
Nor the leaving of Benlomond;
But it's for the leaving of my comrades all,
And the bonny lad that I love so dearly.

According to The Traditional Ballad Index, the song appeared in Vocal Melodies of Scotland in 1841, but no specifics are given. The earliest example I have seen with music is in Christie's Traditional Ballad Airs, vol. I, 1876 p.278, as The bonny, bonny Banks o' the Lomond. Two verses are given, rather different from the form they were later put into by Lady Scott (née Alicia Spottiswoode, 1810-1900). The song quickly became popular and acquired additional verses and a whole extravagant mythology as to its supposed meaning and age. Christie said that he had heard the song in his youth in Buchan, but had paid little attention to it. He considered the melody to be a relative of Kind Robin Lo's Me and The bonniest Lass in a' the Warld; certainly there are noticeable resemblances in the case of the former as it appeared in Johnson's Scots Musical Museum (vol. 5, 1796, no.478). There is also some resemblance to Miss Admiral Gordon's Strathspey, to which Burns set his I love my Jean in 1788.

Christie also published a set of Geordie (Child 209H) in volume 2 of his book, which begins

Will ye go to the Hielans, my bonny lad,
Will ye go to the Hielans, Geordie?
Though ye tak' the high road, and I tak the low,
I will be in the Hielans afore ye.

There doesn't seem so far to be any particular reason to date Loch Lomond earlier than the first few decades of the 19th century, though the tune is older. Red is the Rose, on the other hand, seems to have appeared "in public", so to speak, only in the second half of the 20th century, though anecdotal evidence would take it back as far as the early decades of the century in Ireland. How long has it been known in Newfoundland? None of the major folk song collectors who have worked there seem to have found it, and the Roud Folk Song Index currently lists no examples at all from anywhere.