It is important that, in the definition you provide, the matrix lives in a finite field, say $\mathbb{Z}_m$ where $m$ is prime. This allows you to use Euler's theorem to compute the double-exponentials $a^{q^e}\mod m$ that appear in the matrix in time $O(\log (mn) \; M(\log m))$.
$$a^{q^i}\equiv a^{q^i\pmod{\varphi(m)}}\pmod m$$
Otherwise, it seems hard even to compute the matrix coefficients without factorising $m$.
If $m$ is prime or can be efficiently factorised, the worst-case complexity is dominated by the number of steps you need for matrix multiplication $O(n^\omega)$. For instance, the Smith normal form approach I mentioned in the partner post would compute the determinant in time $O\left( n^\omega \; \log^2m\; \log (mn) \right)$ if you use "slow" multiplication algorithms$^*$. $\omega$ can be chosen to be 2.373.
You get a slow-down in Moore vs Vandermonde since you must double-exponentiate the coefficients of the matrix. When you can factorise $m$ this slow-down is just polylogarithmic on $m$. If not, the algorithm presented gives you a Cook reduction to Double-Modular-Exponentiation on $\mathbb{Z}_m$.
Note *: faster algorithms for integer multiplication allow you to replace $\log^2 m$ with $M(\log m \log\log m)$ .
Update: on the possibility of achieving $O(n\log^a n)$.
I have no definite answer for this, but I found some information that may tighten your search.
Algorithms for structured matrices that compute quantities like determinants in time $O(n\log^a n)$ are called "superfast" in the literature. All known "superfast" algorithms for structured matrices (Vandermonde, Toeplitz, Hankel) seem to rely on a common property of this matrices known as low "displacement rank". Confer the discussion on the first chapter of this book (open access pages), or in this article [ACM],[PDF].
From what I read, given a $m\times n$ Moore matrix $M$, if you were able to find matrices $A$, $B$ such that the new matrix $L(M)=AM-MB$ (or alternatively $L(M)=M- AMB$) has the following structure
$$L(M) = \sum_{k=1}^r g_k h_k^T $$
, and the rank $r>0$ is small (either constant or bounded by $o(\text{min} \;\{m,n\})$), then you can apply existing techniques (check chapter 5 of the book, open-access pages) to triangularise $M$ and, hence, compute $\det{M}$, using $O(n\log^2 n)$. Above, the $g_k$, $h_k$ denote vectors. If you can not find the book above to read the whole thing, this article has also a lot of information about these methods.
Unfortunately, I have no been able to find a low-displacement-rank structure for the Moore matrix (Vandermonde has). The main complication here seems to arise from the "non-linear" nature of the double exponential. If it helps, the cases for Vandermonde, Cauchy, Toeplitz, Hankel are worked out in the book.
