If your IMAP mail server does not yet support IMAP's "move" feature which was introduced in January 2013, Evolution "moves" messages by copying and deleting emails. Deleting means "marking messages for deletion" so all the original messages are retained until you expunge the emails marked for deletion.

See the topic on deleting emails for instructions on how to expunge email messages. Note that this applies to other types of accounts as well.