Thanks O'Meara, but it definitely wasn't the Scottish Soldier. The lyrics I'm thinking of started something like,

"Tell the story
Of the tunes of glory,
And an old scots song
As we gaily march along..."

Or a reasonable facsimile thereof...... A damned good tune and a brilliant swaggering march. I seem to recall the words fitted it perfectly.