With User Story Mapping, If we start our sprint with the MVP, by definition the stories will be musts. In a fixed time-scale without shoulds and coulds, then how can we hit our targets if estimated velocity were to slip?
Usually in scrum, a feature delivered in a sprint would be a mix of musts, shoulds and coulds, allowing leeway for the PM to de scope some stories to keep on time-line.
I would look on a Story Map as on probability distribution. If the team decreases velocity in one sprint, it still have the room to increase it in the next one and deliver MVP in total, meeting the deadline.
So first thing is to "pretend" it's MoSCoW, so when you plan, work on 60% velocity (this is before you've given a commitment to the fixed end date), better to over deliver than just meet the requirement. Once you are going, if you can't descope, you need to do the effort/quality thing. Look at your team and plan early to get extra resource (you ideally need people from inside so little/no ramp up, or screen carefully when bringing in), plus you need to think early about extra hours and if they help (a few here and there is better than a death march in the last month).
Also you need to pare work down to the bone. Agile is about YAGNI etc, but I mean everything, preemptive design, refactoring, test coverage etc. The MVP is a MINIMUM, so do only what you need. raise stories if something will need to be revisited later, just make sure you agree with the PO to spend a percentage time once the MVP is out and making money to clean up.
And if that's unpalatable, you need to remember something has to slip, and you are sacrificing quality in a controlled way you can fix later, better than team cutting corners on the fly to meet the deadline.
