The association between the willow (which grows best in damp places), water, the moon, and hence ocean tides, goes back to Greek mythology where the priestesses of the god Helike (the nurse of the infant Zeus) used willow and water in their rituals.
There is also the Biblical reference in Psalm 137 to the captured Jews who were in exile. The translation of the 1611 King James Version is: "By the rivers of Babylon, there we sat down, yea, we wept, when we remembered Zion. We hanged our harps upon the willows in the midst thereof."
(Note: "willow" is probably a mistranslation - the Biblical trees were more likely to have been the Euphrates Poplar (Populus euphratica) than some species of willow (Salix).)
The reference to Psalm 137 would have had associations with the music of Negro Sprituals, where the "river of Babylon" was a common metaphor for the boundaries between this world and the next, between slavery and freedom, and between the North and South of the USA.
Note: Don McLean's song "Waters of Babylon" was a decade later than Presley's "It's now or never".