I feel like the other two answers are not satisfying from a mathematical point of view, respectively due to their brevity or dogmatic nature. I will describe two ways in which the complex numbers are connected to the phase-space representation of quantum mechanics.
In classical mechanics, phase space is represented by a symplectic manifold. But to make things more concrete, imagine a symplectic vector space. In finite dimensions, symplectic vector spaces over a field $\mathbb{K}$ can be regarded as vector spaces $\mathbb{K}^{2n}$ equipped with a linear map $\omega_n:\mathbb{K}^{2n}\oplus \mathbb{K}^{2n}\to \mathbb K$ such that $\omega_n\!\left(\begin{bmatrix} \vec p_A\\ \vec q_A\end{bmatrix}, \begin{bmatrix} \vec p_B\\ \vec q_B\end{bmatrix}\right):= \vec q_A\cdot \vec p_B - \vec p_A \cdot \vec q_B$ called the symplectic form.
Taking $\mathbb{K}:=\mathbb{R}$ this grading $\mathbb{K}^{2n}\cong \mathbb{K}^{n}\oplus \mathbb{K}^{n}$ corresponds to dividing the space of possible configurations of $n$ particles into $n$ positions and $n$ momenta. The symplectic form captures the degree of commutation determined by the positions and momenta of particles.
A state is determined by a maximally commuting subspace of a symplectic vector spaces (a Lagrangian subspace). The unitary evolution of the state is given by linear maps which preserve the symplectic form (symplectomorphisms). If one regards states as the equally likely possible positions and momenta, the unitary evolution corresponds to the invertible nondeterminstic evolution.
Notice already that the symplectic plane $(\mathbb{R}^2,\omega_1)$ is very similar to the complex plane $\mathbb{C}$ if you regard the position basis to be the real line, and the momentum basis to be the complex line. The transformation that takes the position basis to the momentum basis is given by the Fourier transform. Which is conceptually, very much like the scalar $i$. For example given any rotation of the complex plane $e^{2\pi i \theta}$, there is a real symplectomorphism which rotates the real symplectic plane by $\theta$. The complex conjugation which undoes this rotation corresponds to negating the momentum coordinates in a symplectic vector space, corresponding to the symplectomorphism $(\mathbb{R}^{2n},\omega_n)\to (\mathbb{R}^{2n},\bar\omega_n:=-\omega_n)$.
This is not where the relationship between phase space and complex numbers ends. The attempt to take the phase-space formulation of classical mechanics and adapt it to quantum mechanics is a particular kind of quantization procedure. To get a quantum-version of position and momentum which behaves more or less like in the classical setting, one must apply the Wigner tranformation to the quantum state. This turns a quantum state $|\phi \rangle\in L^2(\mathbb{R}^n, \mathbb{C})$ into a quantum state $W_{|\phi \rangle}\in L^2(\mathbb{R}^{2n}, \mathbb{R})$. So the idea is that now we have doubled the dimension of our space to account for the possible values of positions and momenta. And we have shifted the complexity of the image of $|\phi \rangle$ to the extra dimension for momentum in $\mathbb{R}^{2n}$. This is a continous transformation, but now, unlike in the classical case $W_{|\phi \rangle}$ can produce negative real numbers, so that it is not a probability. Rather, it is a quasiprobability distribution.
In quantum computing, the more you can avoid the negativity, in general the easier the circuit is to build. Therefore, there has been lots of interest for circuits/states whose Wigner transformations are honest probability distributions. In finite dimensions, imposing this restriction on the discrete analogue of the Wigner representation is exactly the stabilizer/Clifford fragment of finite, odd-prime dimensional quantum mechanics. If you take the symplectic conjugate which I described earlier, this corresponds to complex conjugation in this projective representation into finite dimensional Hilbert spaces. So here, the extra dimension for the momentum is really accounting for this complex behaviour.
In the continuous case things are more complicated, but there is conceptually still quite similar. If you take a Lagrangian subspace of $(\mathbb{R}^{2n},\omega_n) $ and invert the Wigner transformation, you do not get a continuous map. In order to obtain a quantum state from such a discontinuous one, one applies Gaussian convolution to smooth things out. States obtained in this way are called coherent states, or quantum Gaussian states. It turns out in order to add Gaussian convolution to $(\mathbb{R}^{2n},\omega_n) $, we use the complex numbers again and work with certain kinds of (positive semidefinite) Lagrangian subspaces of $(\mathbb{C}^{2n},\omega_n) $. Here you think of the subspace $(\mathbb{C}^{2},\omega_1) $ which shears by $i$ as the vacuum state, which is the canonical Gaussian distribution on the phase space $\mathbb{R}^{2}$. And the basic idea is that these positive complex Lagrangian subspaces correspond precisely to states which can be obtained by taking a bunch of vacuum states and then applying real symplectomorphisms to them.
One way in which you can see how this shearing by $i$ behaves the same as the Wigner representation of the vacuum is that these are in some sense uniquely determined by their property of being invariant under symplectic rotation. We could have just as well chosen shearing by $-i$ to correspond to the vacuum, because it has this same property, but we can't have both together because it breaks the correspondance with the vacuum.
So in sum, in order to obtain a probabilistic phase-space representation of quantum mechanics... one takes the real numbers and then adds a complex dimension in two different ways. The first corresponding to adding an extra dimension to position to obtain momentum, and the second time, you add a complex dimension in an orthogonal direction in order to represent Gaussian probability distributions on the space of positions and momentums.
We are by no means the first people to think of this, but me and my colleagues recently wrote an article on this subject which includes various references which people might find useful.
I have necromanced this thread, but I think this needed a proper answer. I can expand this answer further with references if anyone would find it to be useful.
