An invoice is a request for payment that contains information necessary to remit payment to the issuer. Normally that would include the issuer's name, address, terms of payment and if necessary an account number. The invoice also is given a number - a unique key identifier with respect to the issuer.
Later, this number can be referred to in future correspondence. A bill may or may not include any of the above, but an invoice usually will.
Rather, the distinction between these two words is more a matter of custom and the business in question being transacted. For example, a lawyer bills a client, for billable hours. In the abstract, "you should pay your bills on time." Work that is commissioned will usually generate an invoice.
Bill in the sense we're discussing is Anglo Saxon and dates from the 1400s, and invoice is French (envoyer, "dispatch") from the 1500s. You might make the case that invoices are attached to things that are delivered, but in practice it seems that various trades over time have selected one term or the other by tradition and custom.