G'day,
These songs are versions of Child ballad #53, which tells a fairly commonplace legend from the middle ages based on stories by/about pilgims/crusaders who had returned from the holy land. Independantly of the early versions of the song there was also a legend about Gilbert Beket (Child's spelling) which told a fairly similar tale.

Child says "That our ballad has been affected by the legend of Gilbert Beket is altogether likely."

So the song is a melding of similar tales and I suppose it's usually associated with Becket. A version of the legend that I read has the Saracen's daughter being baptised on reaching England and having her "outlandish" name being replaced by a Christian name. If we like to think that name was Matilda fine, but I think we shouldn't expect this song to be completely true to the real Becket story.

Child also says in a footnote that not all historians agree that Gilbert Beket's wife was named Matilda.

Child has 14 versions of this ballad, Bronson has over 100. Child also relates the Gilbert Beket legend. If you don't mind a long post I might put it in here sometime soon.

Cheers,
Alan