The one on my 560SEL ....
.... is retained by a couple of tabs on the socket in the middle of the long side of the relay. They are like backwards pointing shark's teeth.
You can overcome these by rocking the relay to and fro (in the direction the car points) while pulling up.
If that doesn't work, try inserting a thin steel rule, its flat side in contact with the relay's body, vertically in to the socket and prying gently as you rock the relay. That should free the one side and then the other will give.