Check out the track listing for his new Christmas album, If On A Winter's Night, which contains The Cherry Tree Carol, The Snow it Melts the Soonest, a Soul Cake song, and others.

Bizarrely, the Soul Cake Song is credited to (Music & Lyrics by Paul Stookey, Tracey Batteast and Elene Mezzetti), whereas the others are listed as Trad.

http://www.sting.com/discog/?v=so&a=1&id=571

Ah - they've inserted the word "Christmas" - that will explain why it's not traditional. ;)