You are correct: it is per token issued. Token validation is done without contacting Auth0 (except for the first validation which retrieves the signature verification keys), we do not count how many times you validate.
Be sure to cache M2M tokens so you don’t use too many.
Does it mean if we just create an M2M API for one of our clients and their developer requests a new token every hour (by mistake), it will count as our quota? How can we handle this situation?
Yes, any M2M token that is issued for non-Auth0 APIs (i.e. anything not scoped to the management API or authentication API) will count against your quota, even if they are a third party.
We don’t currently have a built in feature for handling this, but there is a feature request you can upvote.