The melody of King Henry is printed in Bronson's The Traditional Tunes of the Child Ballads. Bronson gives as his source the Ritson-Tyler-Brown Manuscript, pp. 85-90, Harvard College Library, and it was collected from Mrs. Brown of Falkland, Aberdeenshire.

Roy Bailey's version of Brian Pearson's Song of the Leaders is on his 1982 album Hard Times, and he was accompanied on this track by John Kirkpatrick. Now, John was with Steeleye Span in 1977, and so he might have known King Henry from them and given the melody to Roy Bailey. But that's pure guessing, and I don't know when Brian Pearson wrote Song of the Leaders and if he already used this meloody or if it was added by Roy.