Let us generalize from four space-time dimensions to a $d$-dimensional Clifford algebra $C$. Define
$$\tag{1} p~:=~[\frac{d}{2}], $$
where $[\cdot]$ denotes the integer part. OP's question then becomes
Why must the dimension $n$ of a finite dimensional representation $V$ be a multiple of $2^p$?
Proof: If $C\subseteq {\rm End}(V)$ and $V$ are both real, we may complexify, so we may from now on assume that they are both complex. Then the signature of $C$ is irrelevant, and hence we might as well assume positive signature. In other words, we assume we are given $n\times n$ matrices
$\gamma^{1}, \ldots, \gamma^{d}$, that satisfy
$$\tag{2} \{\gamma_{\mu}, \gamma_{\nu}\}~=~2\delta_{\mu\nu}{\bf 1}, \qquad \mu,\nu~\in~\{1,\ldots d\}. $$
We may define
$$\tag{3} \Sigma_{\mu\nu}~:=~ \frac{i}{2}[\gamma_{\mu}, \gamma_{\nu}] ~=~-\Sigma_{\nu\mu}, \qquad \mu,\nu~\in~\{1,\ldots d\}. $$
In particular, define $p$ elements
$$\tag{4} H_1, \ldots, H_p, $$
as
$$\tag{5} H_r ~:=~\Sigma_{r,p+r}, \qquad r~\in~\{1,\ldots p\}. $$
Note that the elements $H_1,\ldots, H_p$, (and $\gamma_d$ if $d$ is odd), are a set of mutually commuting involutions.
Therefore, according to Lie's Theorem, then $H_1,\ldots, H_p$, (and $\gamma_d$ if $d$ is odd), must have a common eigenvector $v$.
Since $H_1,\ldots, H_p$ are involutions, their eigenvalues are $\pm 1$. In other words,
$$\tag{6}H_1 v~=~(-1)^{j_1} v, \quad \ldots, \quad H_p v~=~(-1)^{j_p} v, $$
where
$$\tag{7} j_1,\ldots, j_p~\in ~\{0,1\} $$
are either zero or one.
Apply next the $p$ first gamma matrices
$$\tag{8} \gamma^{1}, \gamma^{2}, \ldots \gamma^{p}, $$
to the common eigenvector $v$, so that
$$\tag{9} v_{(i_1,\ldots, i_p)}~:=~ \gamma_{1}^{i_1}\gamma_{2}^{i_2}\cdots\gamma_{p}^{i_p} v, $$
where the indices
$$\tag{10} i_1,\ldots, i_p~\in ~\{0,1\} $$
are either zero or one.
It is straightforward to check that the $2^p$ vectors $v_{(i_1,\ldots, i_p)}$ also are common eigenvectors for $H_1,\ldots, H_p$. In detail,
$$\tag{11} H_r v_{(i_1,\ldots, i_p)}~=~(-1)^{i_r+j_r}v_{(i_1,\ldots, i_p)}.$$
Note that each eigenvector $v_{(i_1,\ldots, i_p)}$ has a unique pattern of eigenvalues for the tuple $(H_1,\ldots, H_p)$, so the $2^p$ vectors $v_{(i_1,\ldots, i_p)}$ must be linearly independent.
Since
$$\tag{12} \gamma_{p+r}~=~ i H_r \gamma_r, \qquad r~\in~\{1,\ldots p\}, $$
we see that
$$\tag{13} W~:=~{\rm span}_{\mathbb{C}} \left\{ v_{(i_1,\ldots, i_p)} \mid i_1,\ldots, i_p~\in ~\{0,1\} \right\} $$
is an invariant subspace $W\subseteq V$.
This shows that that any irreducible complex representation of a complex $d$-dimensional Clifford algebra is $2^p$-dimensional.
Finally, we believe (but did not check) that a finite dimensional representation $V$ of a complex Clifford algebra is always completely reducible, i.e. a finite sum of irreducible representations, and hence the dimension $n$ of $V$ must be a multiple of $2^p$.
