How to Delete Emails

Hi,
I have been using eM Client for several years and have accumulated thousands of emails in various folders. When I try deleting they do not seem to permanently go. I have a Gmail address so do I have to delete from Gmail first. It would be more difficult to do this as Gmail only shows about 50 emails at a time.
Alternatively, perhaps I should delete from “All Mail” but would that delete duplicates in various folders?
My program is running really slow so I expect it is seriously clogged up.
I would really appreciate any advice
Regards,
John.