It really depends on your definition of "murder ballad."

In the Traditional Ballad Index, I have articles on seven different songs that have been proposed as "The Earliest English Ballad." Three of these, "Edward the Martyr" (c. 975), "Judas" [Child 23] (c. 1200), and "Sir Aldingar" [Child 59] (c. 1400). I personally would not consider "Edward the Martyr" a ballad. "Judas" involves a death by malice, but not directly, and there is argument about whether it's a ballad. I don't think there is much question but that "Sir Aldingar" counts.

Also from before 1500 are "The Gest of Robyn Hode" [Child 117], which ends with the murder of Robin, and "Robin Hood and the Monk" [Child 119] which features multiple murders.

If you want something with a precise date, it gets a lot harder. But you could try Steve Gardham's Earliest Reference database and decide for yourself which ones are murder ballads. It seems as if most of what he has is from the late eighteenth century, though, and we obviously have items older than that.