Yes, it is a total SCAM. They probably want you to cash the check, keep some for yourself, and send the majority of the money to someone else, probably through Western Union. Once the money has been sent, the check is no good.
Legitimate companies do not send money to total strangers who have not applied to work for them. Before a legitimate company contacts a shopper, the shopper will have registered and provided a social security number (because any payment is taxable). Legitimate companies do not pay in advance, they pay AFTER a job is completed. Mystery shopping fees are not high. The majority of assignments pay $10-15.
If it sounds too good to be true, it probably is.