At least in the EU, they run the (qualified) risk of a collosal statutory fine. It wouldn't be easy to get them audited (particularly in Ireland where the Data Protection Commission favours discretion over valour), and they'd have to actually get caught. Assuming that they didn't hide the evidence, and the auditors found it, and the necessary hoops were jumped, it could be financially and reputationally painful, even for big G.

If so, why believe "don't save location history" would mean anything either?

I believe according to their privacy policy and from past press statements deleting the data does trigger a real wipe of the data but I think there is a up to 30 day delay (not sure exactly) (wiping data from thousands of servers is actually kind of difficult).

If your threat level is NSA/nation state then this isn't good enough since they probably could get a copy before Google deletes it but it is probably enough to be useless for low level LE.