You can always do $\mathbb{Z}/2$ Morse homology, because then your manifold is guaranteed to be orientable with respect to your coefficient system, and so it's got to be that $H_0(M;\mathbb{Z}/2)=\mathbb{Z}/2$ and $H_n(M;\mathbb{Z}/2)=\mathbb{Z}/2$. So not only do we know we have critical points of index $0$ and $n$, but we know that they actually have to descend to generators in homology. This means that all differentials in our Morse complex will be zero, so generators in the complex are the same as generators for homology. This proves that the last guy has to be in dimension $n/2$.* As you point out, this means that $M$ is homeomorphic to $S^{n/2}$ with an $n$-cell attached.
*** Just to put what I said in the comments right here in the answer: This last critical point has some index $k\in [0,n]$, and it becomes a generator of $H_k(X)$ (with coefficients, if you'd like). But it's trivial to see that when $f$ is a Morse function then $-f$ is a Morse function too, and that this critical point of index $k$ will become a critical point of index $n-k$ for $-f$. And $-f$ equally well satisfies what I just said, i.e. all its critical points become homology generators too. So if you believe that (Morse) homology is a topological invariant, then it must be true that $n-k=k$.
Edit: As Jason explains in answer to my related question, the only manifolds this question can even apply to are homotopy equivalent to $\mathbb{R}P^2$, $\mathbb{C}P^2$, $\mathbb{H}P^2$, and $\mathbb{O}P^2$! Crazy.