@Panma I took it that it was their fate to kill him, so his curse 'ate' that fate (meaning they couldn't kill him, so he killed them easily while they were reeling about their failure). And presumably, as soon as the owner of the eaten fate died, his curse got hungry again (since the fate left the world completely) and could trigger on the next one. Occasionally picking out his allies as well (he was fated to die in a battle three years hence, but now he got killed right away). Given his fighting style and how he didn't seem to know about his superhuman healing abilities, it might be that most kills around him was actually friendly fire somehow..?
Anyway, then this girl came along, fated to be killed by him. And when that fate disappeared, she did not disappear, hence his curse is still masticating on that fate and not snacking on anyone else. Meaning that suddenly he has to fight completely on his own. (And apparently he's so happy about 'not everyone around him dies right away' that he tries to avoid killing people, which might also make things harder upon him.)