In reply to Sam Mills:
Lluc is €5 a night all year round which, frankly is astonishing value. It’s a bit far from the SE but near some great crags.
There is a private campsite called Campamento Hipocampo on the south coast which I recall having good facilities, being pretty reasonable and having two massive dogs. It doesn’t have much of a web presence but it looks like it’s still there. Im sure there are others.
You could sleep on the beach at Cala Barques or in the grottty cave but, assuming you’re hiring a car I wouldn’t want to leave it anywhere near the that beach for any length of time, particularly not with anything in it.