Here are some elements to solve the question.
1st step. Extend $M_p$ as a $(2\ell)\times(2\ell)$-matrix $N_p$, with the same definition of entries. By the way the entries may be writen as $a_{j,k}=p(2\left\{\frac{jk}p\right\}-1)$ where $\{x\}=x-\lfloor x\rfloor$ is the fractional part of $x$. Remark that $a_{j,p-k}=-a_{j,k}$ and likewise $a_{p-j,k}=-a_{j,k}$. Remark that $a_{j,k}$ depends only upon the product $jk\mod p$, thus can be written $a_{jk}$ instead.
Therefore
$$N_p=\begin{pmatrix} M_p & -M_pF \\ -FM_p & FM_pF \end{pmatrix}=\binom{I}{-F}M_p\begin{pmatrix} I & -F \end{pmatrix}$$
where $F$ is the anti-unit matrix, $f_{j,k}=\delta_j^{\ell+1-k}$.
2nd step. From the formula above, $N_p$ and $M_p$ have the same rank. Thus $M_p$ is invertible if and only if $N_p$ has rank $\ell$. This rank is unchanged by a permutation of rows. Thus we examine instead the matrix $N_p'$ obtained by the involution of rows given by the inversion $j\mapsto j^{-1}$ $\mod p$. That way, the entries of $N_p'$ are the numbers $a_{j^{-1}k}$.
3rd step. The matrix $N_p'$ is diagonalizable, its eigenpairs being explicit, because this is a group matrix (entries of the form $a_{g^{-1}h}$) for the multiplicative group ${\mathbb F}_p^\times$ (the non-zero elements of ${\mathbb Z}/p$). Recall that because ${\mathbb Z}/p$ is a field, this group is isomorphic to the additive group ${\mathbb Z}/2\ell$ : there exists an element $\theta\in{\mathbb Z}/p$ of order exactly $2\ell$, and an isomorphism is $\psi(k)=\theta^k$ ($k\mod2\ell$, $\theta^k\mod p$).
The eigenvectors $v^\omega$ have coordinates
$$v^\omega_k=\omega^{\psi^{-1}(k)},\qquad 1\le k\le2\ell,$$
where $\omega$ is any complex solution of $\omega^{2\ell}=1$. The corresponding eigenvalue is
$$\lambda_\omega=\sum_{r=0}^{2\ell-1}a_{\psi(r)}\omega^r=:Q_p(\omega).$$
4th step. There remains to see that among these $2\ell$ eigenvalues, $\ell$ of them only vanish, so that $N_p$ has rank $2\ell-\ell=\ell$. I leave this as an open question (though I am rather optimistic). At least, the fact that $\ell$ of them vanish is clear, because we have $\theta^\ell=-1$, hence $\psi(k+\ell)=-\psi(k)$. There follows that $a_{\psi(k+\ell)}=-a_{\psi(k)}$, so that $Q_p$ factorizes:
$$Q_p(X)=(X^\ell-1)R_p(X),\qquad R_p(X)=\sum_{r=0}^{\ell-1}a_{\psi(r)}X^r.$$
Thus $\lambda_\omega=0$ for every root of $\omega^\ell=1$. Thus there remains only to prove that if instead $\omega^\ell=-1$ (the other roots of unity), one has $R_p(\omega)\ne0$. I have done a few calculations for small prime numbers $p$, which make me optimistic.
Edit. One can conclude at least when $\ell$ is a power of $2$ (that is when $p$ is a Fermat prime). Because then $X^\ell+1$ is irreducible over $\mathbb Q$, while $R_p\in{\mathbb Z}[X]$ has degree $\ell-1$, hence they cannot share a root.
In the general case, the question reduces to whether some cyclotomic polynomial $\Phi_m$ with $m|\ell$ can be such that $\Phi_m(-X)|R_p(X)$. Notice that $\Phi_m$ is reciprocal, while $R_p$ is not, thus this divisibility will imply some other ones, ...
