There is another song, "The Heidless Cross" by George Weir which begins, "Red is the rose that blooms sae braw, Where yorlins sing sae clearly, Grey is the cross that's shorn in twa', where yince we lo'ed sae dearly." Recorded by the Corries on "Strings and Things". Does this sound anything like the song you are looking for.