From Trefethen's NLA:
$A$ is a matrix whose singular values are 1 but whose eigenvalues are the $m$th roots of unity that surround the origin. Hence GMRES requires $m$ steps for convergence and CGN takes 1 step.
Am I to believe that GMRES converges in a number of steps equal to the number of distinct eigenvalues of the system? If so, why?
For instance if I had a $n \times n$ matrix $A$ with $\sqrt{n}$ eigenvalues then would I be correct in saying that GMRES converges within $\sqrt{n}$ iterations?
I can't find the statement you have however it is misleading.
No, if you look at how GMRES is designed it is based on the Arnoldi algorithm. We want the following.
It says let $ \mathcal{K}_{n}$ be the $m \times n $ Krylov matrix and our problem is to find a vector $c \in \mathbb{C^{n}}$ such that
$$ \| A \mathcal{K}_{n} c - b \| \tag{1} $$
The Krylov method is numerically unstable because of linear independence in the columns so you use the $QR$ method it showed before
$$ \| A Q_{n} y - b\| \tag{2} $$
then this becomes
$$ \| Q_{n+1}\hat{H}_{n} y - b \| \tag{3} $$
$$ \| \hat{H}_{n}y - Q_{n+1}^{*} b \| \tag{4} $$
this finally is
$$ \| \hat{H}_{n}y - \| b \| e_{1} \| = \| r_{n} \| \tag{5} $$
So at each step, we are checking $ \| r_{n}\|$ which is the residual. The number of steps required is based on the condition number of the matrix as well. The relationship is given here
$$ \kappa(A) = \frac{\lambda_{max}}{\lambda_{\min}} \tag{6}$$
So, it is related to the number of eigenvalues because if there are not many eigenvalues then it doesn't have to find any. All it is doing is constructing a low-rank approximation through an eigenbasis.