“Deleted messages” are, well, messages that have been deleted in Elasticsearch.
Graylog itself doesn’t ever delete messages, so it has to be some external process deleting the documents in Elasticsearch directly.
The information itself comes from the Elasticsearch Indices Stats.