Simpson The British Broadside Ballad And Its Music quotes versions of the tune from The Dancing Master (1651) and other C17th and C18th sources.

He quotes a song 1656-1659 "Ho, the Broome, The Bonny, bonny Broome" in BM Ms and goes on to state "perhaps the earliest ballad that can be associated with the tune is "The New Broome", beginning "Poore Coridon did sometime sit" (Pepys, also Roxburgh, without tune direction, but with smilar stanza pattern and chorus).

The ballad you give "The lovely Northern Lass", beginning "Through Liddersdale as lately I went" ("To a pleasant Sctoch tune called "The broom of Cowdon knowes") was entered in the Stationers' Register in 1632 according to Simpson.

However, re your Scotch origin, Simpson says "Chappell (PMOT...), anxious to minimize the Scotch element in early balladry, is probably correct here in insisting that the tune is called Scotch because of the subject matter of the ballad. All the evidence points to the British origin of the tune, for it appears exclusively in English publications until the first quarter of the eighteenth century"

Child on the other hand speaks rather deprecatingly of the English ballad (which he gives as an appendix) "The Scottish ballad could not have been developed from a story of this description. On the other hand, it is scarecely to be believed that the author of the English ditty, if he had known of the Scottish ballad, would have dropped all the interesting particulars. It is possible that he may have just heard about it, but much more likely that he knew only the burden and built his very slight tale on that"

Bronson says of the ballad "When this ballad first began to be recorded, in the second half of the eighteenth century, it had, apparently, no refrain or burden...Nevertheless, it is clear that the musical tradition of the ballad in integral with that of the old song-tune which is intimately associated with this burden from its first appearance in the middle of the seventeenth century"

Mick