That's an interesting association about 'bill,' and there may be some distant connection in the etymology.
The more immediate meaning is that the bill, or playbill, was the printed poster that was put up on walls to advertise the actors in a touring drama production, in the centuries when acting companies traveled from one town to the next, before movies were even invented. So 'top billing' meant having one's name in the star's position, at the top of the advertising poster, just as now it means having one's name at the top of the credits and/or the trailer. (-:
I don't know exactly how 'credits' evolved to have this meaning, but that's also an interesting observation. You probably know that to have good credit is in a sense to have a good reputation or good name recognition, so that people believe (credere) you will pay what you owe.
LEO has an entry of sorts, but it should really be one word, not two.