That's a whole system design interview question right there 😉
Fundamentally, if you need that level of detail and fidelity, you compromise on timeliness. You (somehow) record an event for every message sent, then tally those up on a daily or monthly basis.
It depends on the system and the details of your requirements. I would start by looking at how messages are being sent to begin with. For example, if there's a job in a database, you might be able to count the jobs marked as completed right there.
If the message system is fed by a Kafka topic, and you can get away with billing for messages attempted to send, you can count those from the source topic.
You can also explicitly record events, say into another Kafka topic or a database table. You will need to make some choices about CAP un that case: if recording the event fails, do you want to send anyway? What if you're not sure recording it worked?