How exactly are you deleting messages?
AquaMail has three ways (with different looking "delete" icons) -- "move to deleted" (the default), "delete immediately" and "hide in the app, keep on the server"; this is a per-account setting (Manage accounts -> Tap on your account -> Options -> Account options -> Deleting messages).
Of these, "hide" does not touch the server at all.
If you're using "move to deleted", please check the "mapping" between Aqua's "[ Deleted ]" folder and server folder:
Long press the account -> options and folders -> folders
Find the server side Deleted (Trash, Bin, Deleted Items, etc) tap it and choose "Sync with [ Deleted ]".
Cheers,
Radoslav