Maybe Wily's ultimate goal isn't to destroy Rock, but rather to destroy his faith in others and in peace. Think about it. Every encounter gives him new powers, makes him more powerful. Every time he faces Wily, he gets a bit less patient with him (heck, he even THREATENS Wily at the end of MM7 - think about THAT, too!). And Wily's ambition, all along, is to use these powerful Robot Masters - Rock being one of them - to conquer the world with their superior power.
Perhaps destroying MegaMan was the goal in his more ignorant days, but it's a far easier thing - and better outcome for Wily - if he simply succeeds in manipulating him, instead. For example, notice the HUGE paradigm shift in Wily between MM8 and MM9. When a creature of such enormous power as Rock ever DOES lose their faith in lasting peace, what do you think *would* become of them? And of course, "frienemies" like Bass/Forte really help that a lot.
(Speaking of Time Paradoxes - does it even really make sense to "chronologicalize" them in the first place?)