G'day,
Professor Child, writing in 1890 (or earlier) says that "Waly, Waly" was known from the first quarter of the eighteenth century. This in his notes on "Jamie Douglas" (Child #204), where he points out the common ground between the former and several versions of the latter.

Bronson says that Allan Ramsay was the first to publish it in Tea-Table Miscellany, c. 1724.

O waly, waly up the bank!
And waly, waly, down the brae!
And waly, waly yon burn-side,
Where I and my love wont to gae!

I leand my back unto an aik,
I thought it was a trusty tree;
But first it bowd, and syne it brak,
Sae my true-love did lightly me.

etc.

Cheers,
Alan