(Anti)Heroes are romantic by nature. They perform heroically, passionately, in order to attain an ideal. I think the issue you might be facing here is not one of writing, per se, but of psychology.
You're probably judging your character.
You presume that because he uses 'harsh' methods, that must be his sole definition. He can't like cake and pie? Coffee and tea? Because you use the term anti-hero, we can further presume that maybe you're only offering clarification for sake of brevity in your question, or it could also point to an underlying belief system you hold, that killing people for any reason is bad. Therefore, MC is an anti-hero.
If that's the case, I think the first thing you need to do is not worry about your subplot, but learn to love your MC. You have to forgive him as an author, and at least in the abstract, embrace his ideals. You aren't going to be able to convince the reader of his conviction and his passion if you're constantly apologizing for him.
He does what he does, because it is the right thing to do. (In his mind.) He is a murderer of murderers, sine qua non, and it is a role he is willing to accept in order to make the world a better place... for those he loves.
The opposite of love is not hate, it is apathy
Do pardon my Rand, but this is true. If you love something, if it matters to you, and it turns into something you find distasteful, that it is the inception of hate, but its core is still love. If something doesn't matter to you, you don't give a shit either way. Shoelaces for example. I doubt you have a heated, passionate feeling towards shoelaces either way. But the naturalistic right to life, on the other hand, likely sparks you strongly, and you have very specific ideas about how that should be addressed.
The point here is that your MC might be angry, spiteful, vindictive, hateful, that does not mean he is evil. While you and I may disagree with his motives, he would argue them to his death, and would have very specific ideas about why what he is doing is right. In his mind, even if he recognizes his actions as questionable, he still finds them justifiable, and therefore good.
So if he's hateful, that's because he loves that which he hates. Hm?
Once you have come to terms with the MC's psychology/philosophy, likely you will see that there is not only a lack of contradiction in a love story mixed into your primary arc, it actually ADDS to the primary arc. Your reader needs to be able to relate to your MC in order to be invested in him. If he's just a single-minded assassin lacking in humanity, you're going to have difficulty pulling that off.
By making him more complex, by adding the fuel of a romance, you have
a million opportunities to draw contrasts and metaphors between his
actions and his values.
How do you handle seemingly contradictory subplots? The same as any other subplot. You lace it into the story. You use it to teach the reader about the world and its characters. Your use it to build empathy for your characters; to draw the reader into your story through the common ground of morality and sexuality, and then leverage it to whatever aims you desire. To humanize the MC. To deliver him. To destroy him.
I think your subplot, as it is, could be even more powerful than your primary arc. (Perhaps not more important, or maybe that too.) I think maybe you're judging your character, and your subplot. Maybe it's not a subplot at all, but the foundation. You just need to tweak your perspective, and you may realize that it's not the plots that are contradictory...