Counting Conjugacy Classes: $A^6 = I$

Please read my comments under the OP's question. In this answer, I would like to only address the case $m=6$, that is, the situation the OP asks for. I do not know how to deal with the general exponent $m$.

As we have established, the characteristic polynomial involved in each indecomposable block of $A$ is one of the following four cyclotomic polynomials: $$\Phi_1(x)=x-1\,,\,\,\Phi_2(x)=x+1\,,\,\,\Phi_3(x)=x^2+x+1\,,\text{ and }\Phi_6(x)=x^2-x+1\,.$$ Now, $A$ must have at least one indecomposable block of size $2\times 2$. Let $a$ and $b$ denote the number of $2$-by-$2$ indecomposable blocks of $A$ and the number of $1$-by-$1$ blocks of $A$. Then, $a\geq 1$ and $2a+b=k$. Denote by $J_1,J_2,\ldots,J_a$ the $2$-by-$2$ blocks of $A$, whereas $K_1,K_2,\ldots,K_b$ the $1$-by-$1$ blocks. We may assume that $J_1,J_2,\ldots,J_p$ have $\Phi_6$ as the characteristic polynomial, whereas $J_{p+1},J_{p+2},\ldots,J_a$ have $\Phi_3$ as the characteristic polynomial. Similarly, suppose that $K_1,K_2,\ldots,K_q$ have $\Phi_2$ as the characteristic polynomial, whilst $K_{q+1},K_{q+2},\ldots,K_b$ have $\Phi_1$ as the characteristic polynomial.

If $p\geq 1$, then there is no restriction on $q$. Thus, for each fixed $a\in\Biggl\{1,2,\ldots,\left\lfloor\dfrac{k}{2}\right\rfloor\Biggr\}$, there are $a$ ways to choose $p\geq 1$ and $b+1=k-2a+1$ ways to choose $q$. Thus, for $p\geq 1$, there are $$\begin{align}\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,a(k-2a+1)&=(k-1)\,\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,a-4\,\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,\frac{a(a-1)}{2} \\ &=\frac{k-1}{2}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)-\frac{2}{3}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)\,\left(\left\lfloor\frac{k}{2}\right\rfloor-1\right) \end{align}$$ corresponding conjugacy classes.

If $b=0$, then $q\geq1$ is required. Thus, for each fixed $a\in\Biggl\{1,2,\ldots,\left\lfloor\dfrac{k}{2}\right\rfloor\Biggr\}$, there are $b=k-2a$ ways to choose $q\geq 1$. Hence, for $p=0$, there are $$\sum_{a=1}^{\left\lfloor\frac{k}2\right\rfloor}\,(k-2a)=k\,\left\lfloor\frac{k}{2}\right\rfloor-\left\lfloor\frac{k}{2}\right\rfloor\,\left(\left\lfloor\frac{k}{2}\right\rfloor+1\right)$$ corresponding conjugacy classes.

This shows that $$N(k,6)=\frac{1}{6}\,\left\lfloor\frac{k}{2}\right\rfloor\,\left(3\,(k-3)\,\left\lfloor\frac{k}{2}\right\rfloor-4\,\left\lfloor\frac{k}{2}\right\rfloor^2+9\,k-5\right)$$ is the total number of conjugacy classes. We have $$N(1,6)=0\,,\,\,N(2,6)=1\,,\,\,N(3,6)=3\,,\,\,N(4,6)=7\,,\text{ and }N(5,6)=12\,.$$ (The OP miscounted something. From his list, there should be $12$ distinct conjugacy classes for $k=5$.)

Note that $$\frac{(k-1)(k^2+10k-3)}{24}\leq N(k,6)\leq \frac{k(k-1)(k+10)}{24}\,.$$ The left-hand side is an equality iff $k$ is an odd positive integer. The right-hand side is an equality iff $k=1$ or $k$ is an even positive integer.

If $A\in M_n(\mathbb{Q}),A^6=I$, then $A$ is diagonalizable over $\mathbb{C}$ and its eigenvalues must be chosen among $1,-1$ or the couples $(j,j^2)$ or $(-j,-j^2)$ where $j=e^{2i\pi/3}$. Since the minimal polynomials of the above eigenvalues in $\mathbb{Q}[x]$ have degree $2$, our matrices are classified by the eligible sequences with elements in the box $ 1, -1, (j, j ^ 2), (- j, -j ^ 2) $, elements encoded by $(1,2,3,4)$, ordered by $1\leq 2\leq 3\leq 4$ with $length(1)=length(2)=1,length(3)=length(4)=2$. One condition is $\sum_i length(i)=k$.

EDIT. The other condition is $order(A)=6$, that is, EITHER the element $4$ is in the considered sequence OR the couple $2,3$ is in the sequence.

Note that the number of similar classes is the same as in $M_n(\mathbb{R})$.

For example, when $k=4$, there are $7$ eligible sequences (then $7$ similar classes) [1, 1, 4][1, 2, 3][1, 2, 4] [2, 2, 3][2, 2, 4][3, 4] [4, 4]

A rudimentary procedure (with computer) gives explicitly the list of the similarity classes and, of course, the number of classes.

For $k=5$, there are $12$ similar classes. [1, 1, 1, 4][1, 1, 2, 3][1, 1, 2, 4] [1, 2, 2, 3][1, 2, 2, 4][1, 3, 4] [1, 4, 4][2, 2, 2, 3][2, 2, 2, 4] [2, 3, 3][2, 3, 4][2, 4, 4]

For $k=6$, $20$ classes.

For $k=7$, $29$ classes.

These results are consistent with the counting Batominovski's formula (thanks to him for pointing out an error in the previous version of my post).