It depends on multiple issues. The word Evolution is a bit red-herring, the same politics works over different devices -- more here with Android -- of course the UI is different with Evolution, go to Edit > Preferences > Sending Email > Defaults > Sent.
IMAP or POP3?
If you use IMAP and multiple devices, please, note that your settings must correspond to each other over every email-client -- more here. If you use some Online-email-client, you must make sure its settinsg are correct -- for example, Gmail Labels set to invisible makes also your Evolution Sent emails invisible. If your server-side email-client such as mutt has a wrong record -field, it means every IMAP email-client will malfunction. If your Gmail filters has some odd Delete It, it may delete all of your sent -emails -- also a possible reason why IMAP -mailbox may not work.
Now POP3 is much simpler. It just directs every email to different mailboxes, meaning you need to replicate your work over multiple devices -- driving you mad if you have many email-clients like me: mutt in Server, Evolution in Desktop, K9 in Android, iOS email in iPad etc. But the good side is that the settings between different email-clients won't intercept one another the way they do with IMAP -configured mailboxes.
Best Answer
In 3.2.2, Ctrl-A (select all messages), Message -> Remove Duplicate Messages works for a folder.