Why are restaurant bills called 'checks'?

Which is perhaps a clue - “waiter’s check” is likely the device by which the waiter checked your order, probably in all aspects: its ordering, delivery and payment.