I learned this has a "Mother Goose" recitation when I was about 2 from my grandmother (it was the way she greeted all her grandchildren, and taught us about the ritual of shaking hands), and it was only one verse:

On a misty, moisty morning,
When cloudy was the weather,
Along came an old man
All dressed in leather.
He began to compiment
And she began to grin.
How do you do, and how do you do, and how do you do again?

(Grandmother would take the hand of the child on the last line and shake it up and down in rhythm of the words -- far better than getting your cheek pinched)

It wasn't until recently that I learned it was a full-fledged song.