Do I need to remove old adhesive residue before installing new self-adhesive flooring?
Check the "surface prep" instructions as it will likely instruct you to remove all previous residue, grease, dust, etc... or else they won't warrant their product.

FYI, removing all of the residue is damn near impossible as you are finding out and if you lay down new peel-n-stick then take a wild guess at what will happen to your new flooring in a few years.

I would probably choose to lay down the thinnest underlayment I can find such as 1/4 inch common plywood so that the project doesn't go to sh1t after a few years.