[CREWZIN]

As you can see from your new one, the old one is held on with 3M double sided tape. You can get hold of a hair dryer and slowly lift off the edge of the step pad and get some heat in the opening (not too hot) and peel off the old one or just try and peel it off without the heat. If done right the only damage to the paint (if there is any) would be under the new pad.

Sometimes we tell owners to use fishing line to get under the edges of parts help on with the 3M tape but I don't think you get under both sides at once to create a sawing motion.