While $M=n^{O_p(1)}$ can be tricky (or out of reach), improving the trivial bound $M\le p^{\varphi((p-1)n)}$ one can show that, indeed, $M\le p^{(2+o(1))\sqrt{(p-1)n}}$ holds. To this end, recall that the *critical number* of a finite abelian group $G$ is defined to be the smallest positive integer $k$ such that for any $k$-element subset $A\subset G\setminus\{0\}$, every element of $G$ is representable as a non-empty sum of elements of pairwise distinct elements of $A$. It is known that the critical number of any finite abelian group is at most $(2+o(1))\sqrt{|G|}$ (just google for the references).

Let now $k$ being the critical number of the group ${\mathbb Z}/((p-1)n){\mathbb Z}$, so that $k\le(2+o(1))\sqrt{(p-1)n}$. If the order of $p$ in this group does not exceed $k-1$, then we have $p^s\equiv 1\pmod{(p-1)n}$ with some $s\le k-1$, implying $n\mid 1+p+\dotsb+p^{s-1}$. Otherwise, consider the set $A:=\{1,p,p^2,\ldots,p^{k-1}\}\subset {\mathbb Z}/((p-1)n){\mathbb Z}$. By the definition of a critical number, one can select several elements from this set so that their sum is equal to $0$, and the claim follows.