Child no. 81 is 'Little Musgrave and Lady Barnard' and Child gives the earliest written citation as 1611 - as given above. It's not unreasonable to suppose that if the ballad is based on historical events then those events could have taken place a century or more earlier - or not, as the case may be.
Interestingly, some versions of Child no. 83, 'Child Maurice' ('Gil Morice', 'Bob Norice', etc., etc.) also feature a homicidal 'Lord Barnard'who, this time, mistakes Lady B's illegitimate son (Child M.) for her lover and chops his head off. This seems to be a much later ballad (printed versions from mid-18th century)but perhaps at some time in the 15th/16th centuries there was a Lord Barnard, in the North of England, who was known to fly off the handle when he thought that his missus was 'playing away' and his savagery stuck in the folk memory and generated (at least) two ballads.