вопрос-почему он должен выполнятся в релятивистской механике?
Ответ "почему бы и нет". Мы должны откуда-то взять законы для новой механики, вот, одна из гипотез - из принципа наименьшего действия. Тем более что он так красиво в Минковском выглядит.
Потом, после принятия этого принципа, можно показать, что релятивистская механика даёт в качестве предела стандартную нерелятивистскую. Значит, гипотеза корректная. Проведя релятивистские опыты (с движением и столкновением быстрых частиц), можно подтвердить и релятивистскую механику per se - что, собственно, и было сделано. Так что принцип наименьшего действия в релятивистской механике
почему-то выполняется - можно считать это за экспериментальный факт.
И откуда вообще он взялся?
Из размышлений, а каковы наиболее фундаментальные законы природы и их математическое выражение. В конце 18 - начале 19 века было обнаружено, что механика, ранее известная только в виде законов Ньютона, позволяет и иное выражение, более простое и компактное (хотя приводящее к решению конкретных задач более долгим путём). Потом аналогичные выражения стали находить в других разделах физики, с механикой не имеющих ничего общего (электростатика, оптика, потом электромагнетизм). Дальше происходило ещё много всякого, и в итоге - это центральная концепция теоретической физики вообще. Рекомендуется ЛЛ-1, если вы его ещё не читали.