So for the key question —

“Bill” from “Will” (short for “William”, of course) was part of a great 13th-14th century English of forming “rhyming nicknames” by swapping the first letter of the original name.

That’s where we get surprising forms like Polly from Molly, Bob from Rob (from Robert), and Hodge from Roger.

Apparently ONE impetus in the letter swapping at that particular time was a dislike amongst the native English for the harsh Norman French “r”. (Note how many nicknames made substitutions for r’s — not only at the beginning of words [Rich(ard) > Dick, Robert > Bob], but in the middle of them — Mary > Molly, Sarah > Sally/Sadie, Dorothy > Dolly; Harold/Harry (> Hal).

One of the most intriguing is the name “Hick” which, along with “Dick” (appearing in writing around 1220) This is preserved not only in the now derogatory term “hick”, but also in the nursery rhyme “HICKORY, dickory, dock”!

http://www.straightdope.com/mailbag/mdick.html

Now some of the letters swapped for the originals seem to be completely random (though there may be some ‘favorites’ used — esp. B, D and H). But others ARE related to the original sound. For example /m/ is closely related to /b/, which becomes a /p/ sound if you say it without the voice (explaining Molly > Polly, Meg [from Marg(aret)] > Peg). In a similar way, the /b/ sound is a “bilabial” (made with the two lips), as /w/ is, and also /m/. Changes amongst these sounds, including /w/ shifting to /b/ (or the related /v/ sound) are not at all unusual. They have taken place in many languages.

For other forms of “letter swapping” to create nicknames, and a variety of other methods by which English nicknames developed see:

http://www.geocities.com/edgarbook/names/other/nicknames.html

And William isn’t always Billy, it can be Will, Willy, or Bill!