Hello Katrine
There seems to be a document selection limit of 2k documents at a time. Selecting more than that and deleting it will result in an error. Can you check by selecting maximum 2K document at a time and then click on delete button, it will prompt confirmation for deletion.
However, if the documents are in trash, those will also gets deleted after time specified for soft-deletion. By default, soft deletions are enabled for mail databases created from the mail template. The default expiration time is 48 hours.
I have collaborated this internally and to properly address this issue, kindly create a case for this as we need information/logs to collect and further investigate this issue.