From Mother Goose's Melodies for Children, Or Songs for the Nursery by Henry Louis Stephens, Gaston Fay. (New York: Hurd and Houghton, 1869), page 113:

The King of France went up the hill,
With twenty thousand men;
The King of France came down the hill,
And ne'er went up again.

[The following comes from an endnote, page 184:]

In a tract, called "Pigges Corantoe, or Newes from the North," 4to, London, 1642, page 3, this is called "Old Tarlton's Song." Richard Tarleton was an actor contemporary with Shakespeare, and was famous for playing the clown in his plays, and in those of others. He died in the year 1588. A common variation is the following:—

The King of France marched up the hill,
With twenty thousand men,
And when he got them up the hill,
He marched them down again.