I believe that we can show:
Claim. There's a value $0 < c < 1$ such that the following is true. Suppose there's a deterministic poly-time algorithm that, given an $m$-clause 3-SAT instance $\phi$, outputs a list $S$ of at most $m^c$ values, such that $M(\phi) \in S$;
then the polynomial hierarchy collapses.
The proof uses Fortnow and Santhanam's results on infeasibility of instance compression from their paper
http://www.cs.uchicago.edu/~fortnow/papers/compress.pdf
Specifically, by looking at their proof of Thm 3.1, I believe one can extract the following (I will re-check this soon):
"Theorem" [FS]. There are integers $0 < d' < d$ such that the following is true. Suppose in deterministic poly-time, one can transform an OR of $n^d$ Boolean formulas (each of length $\leq n$, and on disjoint variable-sets) into an OR of $n^{d'}$ formulas (again variable-disjoint and of length $\leq n$), preserving satisfiability/unsatisfiability of the OR. Then $\mathsf{NP} \subseteq \mathsf{coNP/poly}$ and the polynomial hierarchy collapses.
The proof of our claim will be a reduction from the OR-compression task mentioned in the above theorem[FS], to the problem of list-computing $M(\phi)$. Suppose $\psi_1, \ldots, \psi_{n^d}$ is a list of formulas whose OR we want to compress.
First step: define a polynomial-size circuit $\Gamma$ on input strings $(v, y_1, \ldots, y_{n^d})$. Here the string $y_i$ encodes an assignment to $\psi_i$, and $v \in \{0, 1\}^{d \log n + 1}$ encodes a number between $0$ and $n^d$.
We have $\Gamma$ accept iff either $v = 0$, or $\psi_v(y_v) = 1$.
Now let $M^*(\Gamma)$ denote the maximum value $v$, such that the restricted circuit $\Gamma(v, \cdot, \ldots, \cdot)$ is satisfiable. (This quantity is always at least 0).
Suppose we can efficiently produce a list $S$ of possible values for $M^*(\Gamma)$. Then the claim is that in our list $\psi_1, \ldots, \psi_{n^d}$, we can throw away all $\psi_i$ for which $i \notin S$; the resulting list contains a satisfiable formula iff the original one did. I hope this is clear by inspection.
Conclusion: we can't reliably produce a list $S$ of $\leq n^{d'}$ possible values for $M^*(\Gamma)$, unless the poly hierarchy collapses.
Second Step: We reduce from the problem of list-computing $M^*(\Gamma)$ to that of list-computing $M(\phi)$ for 3-SAT instances $\phi$.
To do this, we first run Cook's reduction on $\Gamma$ to get a 3-SAT instance $\phi_1$ of size $m = poly(n^d)$. $\phi_1$ has the same variable-set as $\Gamma$, along with some auxiliary variables. Most important for our purposes, $\phi_1(v, \cdot)$ is satisfiable iff $\Gamma(v, \cdot)$ is satisfiable.
We call $\phi_1$ the `strong constraints'. We give each of these constraints weight $2m$ (by adding duplicate constraints).
Then we add a set of `weak constraints' $\phi_2$ which add a preference for the index $v$ (defined in step 1) to be as high as possible. There is one constraint for each bit $v_t$ of $v$, namely $[v_t = 1]$. We let the $t$-th most significant bit of $v$ have a constraint of weight $m/2^{t-1}$. Since $v$ is of length $d \log n + 1$, these weights can be made integral (we just need to pad to let $m$ be a power of 2).
Finally, let $\phi = \phi_1 \wedge \phi_2$ be the output of our reduction.
To analyze $\phi$, let $(v,z)$ be the variable-set of $\phi$, with $v$ as before.
First note that given any assignment to $(v, z)$, one can infer the value of $v$ from the quantity
$N(v, z) =$ (total weight of $\phi$-constraints satisfied by $v, z$).
This follows from the hierarchical design of the constraint-weights (similarly to a technique from Luca's answer).
Similarly, the maximum achievable value $M(\phi)$ is achieved by a setting $(v, z)$ that satisfies all strong constraints, and where (subject to this) $v$ is as large as possible.
This $v$ is the largest index for which $\Gamma(v, \cdot)$ is satisfiable, namely $M^*(\Gamma)$.
(Note, it is always possible, by setting $v =$ all-0, to satisfy all strong constraints, since in that case $\Gamma(v, \cdot)$ is satisfiable.)
It follows that, if we are given a list $S$ of possible values of $M(\phi)$, we can derive a list of $|S|$ possible values of $M^*(\Gamma)$. Thus we can't have $|S| \leq n^{d'}$ unless the poly hierarchy collapses. This gives the Claim, since $n^{d'} = m^{\Omega(1)}$.