Choose generators $n_1,\dotsc,n_r$ for $N$ with $p^{s_i}n_i=0$. It is not hard to see that the annihilator of $p^{s_i}$ on $M$ is $p^{s-s_i}M$, so we can choose $m_i$ with $p^{s-s_i}m_i=n_i$. If we can prove that the elements $m_i$ form a basis for $M$ over the ring $R/p^s$, then everything else is clear.
The given assumptions on $N$ imply that the elements $p^{s-1}m_i=p^{s_i-1}n_i$ are linearly independent over $R/p$ in the space $M[p]=\{m\in M:pm=0\}$, and by counting dimensions they must form a basis. Multiplication by $p^{s-1}$ gives an isomorphism $M/pM\to M[p]$, so the elements $m_i$ form a basis for $M/pM$ over $R/p$.
We can certainly write $m_i=\sum_ja_{ij}e_j$ for some matrix $A=(a_{ij})$ over $R$, where $e_1,\dotsc,e_r$ is the standard basis for $M$. The above shows that $\det(A)$ is invertible mod $p$. It follows easily that it is invertible mod $p^s$ as well, which proves the claim.
My argument refers to $p^{s_i-1}$ and so does not immediately work if $s_i=0$ for some $i$, but that can be cured with a few more steps.