Is PvP matchmaking done by Soul Level or Soul Memory in Dark Souls 2

The Souls Memory is basically the sum of every soul you've possessed, whether you used it to buy something, to level up, to repair items or simply lost it.

Note: The souls of fallen bosses or the souls you find in corpses (eg. Soul of a Hero) do not count towards your Soul Memory until you actually use them.

Second Note: Answering specifically your question. By the time you lost those souls, they were already part of your Soul Memory, in other words, every single soul you receive adds to your current souls (the ones you have to spend) and your soul memory, what happens to those souls after that doesn't matter, they will stay as part of your soul memory.

As mentioned by @3ventic in the below comment, it is worth noting that the retrieved souls DO NOT add to your soul memory, as those are souls you already acquired.

Cheaters can be handled by leaving That's all you can do, save your game and leave

Report them on Xbox, file a complaint and give them bad player rep File a complaint - Xbox actually have to look into these but the user will have to have several complaints for action to be taken(by different users for the same reason.)

Bad player rep - Starts on their Xbox profile decrease and they get connected to other players who have rep like they do, this also stops them finding you in matchmaking. (This apply's globally, not just to the Dark Souls 2.)

Try not let them get to you that's the main thing, if you get annoyed then the modifier has done what he wanted to do.

Benefit to the modifier is, he gets to have power over you, because basically you are powerless to them, this is what drives them.