The quickest and cheapest way is to do something similar to what you suggested: Every time the user performs a main function of your program, say it's "Pack Widgets onto Warehouse Floor," log that function, with an ID of the individual installation of the program, username and maybe the machine name too. Generate the unique ID on installation - maybe a GUID generated during the installation process.
The reason I say a main function (or several/all main functions) of the program is that they could just start the program once and you will only have one entry for billing. This way you can avoid that scenario, and also have the added side-benefit of seeing which functions of your program which users are actually using the most. This can help your sales team and also your development team target the correct areas.
Make sure that you tell the client that you're going to be billing them based on usage and that the program needs to connect to external servers in order to function. However, you need to make sure that the client's business can continue to function when their internet connection is down. Cache these usage logs locally in an encrypted cache (so that tech savvy clients can't jippo your system easily) and then have a maximum period that the program can function without having an internet connection, say a week or two. After that period, the program will refuse to work unless it connects to your server.
Let's say the client can't connect because a hurricane has taken down the comms for two weeks. In that really bad situation, the client types in a code that you give them over the phone that gets evaluated in your program (NOT something like "give me more time", but a proper code that gets checked by a relatively simple algorithm) and they get another week's grace period. However, I discourage this as it adds unnecessary complexity. If you're concerned about this type of scenario and you're on a monthly billing cycle, rather consider making the cache period three or four weeks.