There is a Database (must be purchased) called pdNickname. I found it via this question: Database of common name aliases / nicknames of people
Searched Google for "nickname database" and it's the second result.
In addition to all that, the transformations - as pointed out by Hunter - are simple. You can implement those transformations in 5 minutes or less. The one you pointed out ("William" -> "Bill") is still quite simple, although you'll need a list of names -> nicknames hence the link to the above Database.
From their sample text
NAME VARIATION GENDER
------------------------------------
ABIGAIL ABBEY 1F
ABIGAIL ABBIE 2F
ABIGAIL ABBY 3F
ABIGAIL GAIL 4F
ABIGAIL ABAEGAYLE 5F
ABIGAIL ABAGAEL 6F
May be a bit of an overkill, but not all "Williams" like to be called "Bill" :P
EDIT
There is also an alternative on Google Code which is a CSV of names and common nicknames/diminuntives.