That "'Ole Bill" suggestion was one of those in the Met list I posted, Walrus.

Another one I haven't seen is that it might be a distortion of "The Peelers", which could well be heard as "The Bills". However if it's correct that it only turned up in post World War II years, that doesn't see too likely, since calling them Peelers in England had died out many years before that.