The number of total messages in a group which Gnus displays in group buffer is by far to high, especially in mail groups. Is this a bug?
No, that’s a matter of design of Gnus, fixing this would mean reimplementation of major parts of Gnus’ back ends. Gnus thinks “highest-article-number − lowest-article-number = total-number-of-articles”. This works OK for Usenet groups, but if you delete and move many messages in mail groups, this fails. To cure the symptom, enter the group via C-u RET (this makes Gnus get all messages), then hit M P b to mark all messages and then say B m name.of.group to move all messages to the group they have been in before, they get new message numbers in this process and the count is right again (until you delete and move your mail to other groups again).