If $n$ is prime, I will show that $Tr(A^r B^s)_{1 \leq r \leq n,\ 0 \leq s \leq n-1}$ is algebraically independent. This is one less the potentially optimal $n^2+1$, since all such traces live in the ring of $GL_n$ conjugacy invariants and that ring has dimension $n^2+1$. Since smaller matrices include into larger matrices, this shows that $Tr(A^r B^s)_{1 \leq r \leq p,\ 0 \leq s \leq p-1}$ is independent where $p$ is any prime less than $n$. By Bertrands postulate, this gets me up to at least $(n/2)^2$ (and $n^2(1-o(1))$ for $n$ large). I suspect that the stated list is always algebraically independent, but I don't want to work more on this.

We recall the use of Jacobian determinants to establish algebraic independence: If $f_1$, $f_2$, ..., $f_r$ are polynomials in variables $x_1$, $x_2$, ..., $x_r$ (and possibly other variables as well), and there is a polynomial relationship between the $f_i$, then $\det(\partial f_i/\partial x_j)$ will be identically zero. (Proof sketch: Implicit differentiation of the polynomial relation.) Thus, if I show that this determinant is nonzero at any point, it shows that the $f_i$ are algebraically independent.

The indices of my matrices will always be modulo $n$. I will consider the above traces as functions of the $n^2$ variables $A_{ii}$, for $1 \leq i \leq n$, and $B_{jk}$ for $1 \leq i,j \leq n$, $k \not \equiv j+1 \bmod n$. I will evaluate the Jacobian at
$$A = \begin{pmatrix} \alpha_1 & & & \\ & \alpha_2 & & \\ & & \ddots & \\ & & & \alpha_n \end{pmatrix} \qquad B=\begin{pmatrix} & 1 & & \\ & & \ddots & \\ & & & 1 \\ 1 & & & \end{pmatrix}$$
where the $\alpha$'s are distinct and nonzero and all unlabeled entries are $0$.

First, observe that (among the variables we are differentiating with respect to), $Tr(A^r)$ depends only on the $A_{ii}$. Therefore, the monomials $Tr(A^r)$ and the variables $A_{ii}$ form an $n \times n$ block in our $n^2 \times n^2$ matrix, and it is well known that this block is invertible whenever the $\alpha_i$ are distinct. So we can concentrate instead on the $(n^2-n) \times (n^2-n)$ matrix which uses the monomials $Tr(A^r B^s)_{1 \leq r \leq n,\ 1 \leq s \leq n-1}$ and the variables $B_{jk}$, $k \not \equiv j+1 \bmod n$.

Fix $s$ and think about $Tr(A^r B^s)_{1 \leq r \leq n} = \sum_i \alpha_i^r (B^s)_{ii}$. As $r$ varies, we get $n$ different linear combinations of the quantities $(B^s)_{ii}$.
Since the $\alpha$'s are distinct and nonzero, this linear transformation is invertible, so we may think instead about the $n^2-n$ functions $((B^s)_{ii})_{1 \leq s \leq n-1,\ 1 \leq i \leq n}$.

Let $k \not \equiv j+1 \bmod n$ and consider $\partial ((B^s)_{ii})/\partial B_{jk}$, evaluated at the $B$-matrix above. It will be zero unless $j \equiv k+s-1 \bmod n$ and $(k,i,j)$ are weakly circularly ordered. In that latter case, it will be $1$.

Thus, the $(n^2-n) \times (n^2-n)$ Jacobian breaks into $n \times n$ blocks. For each block, we fix and $s$ and look at the $n$ functions $(B^s)_{ii}$ and the $n$ variables $B_{jk}$, $j \equiv k+s-1 \bmod n$. This block looks like
$$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & \cdots & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & \cdots & 0 & 0 & 0 \\
& & & & & \ddots & & & \\
0 & 0 & 0 & 0 & 0 & \cdots & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & \cdots & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\
\end{pmatrix}.$$
Here there are $s$ ones and $n-s$ zeroes in each row.
The eigenvalues of this circulant matrix are $1+\zeta+\zeta^2+ \cdots + \zeta^{s-1}$ when $\zeta$ runs through the $n$-th roots of unity (including $1$). If $n$ is prime, all these sums are nonzero, so the determinant is nonzero and we win.

4more comments