One thing we do know about the Robin Hood stories, from the town records of Edinburgh from the late 1400s to the Reformation, is that they were staged. A dramatic performance doesn't need to sing the whole story, ballad-style - you'd expect there to be "numbers" that might have made it into oral tradition directly from the stage. Though they wouldn't necessarily incorporate recognizable chunks of story. Do we have any documented survivals of pieces like that?