If $v$ is not scalar, the ring $\mathbb Z[M]$ generated by $M$ has rank $2$ over $\mathbb Z$. It is therefore either an order in a number field, a finite-index subring of $\mathbb Z^2$, or $\mathbb Z[\epsilon]/\epsilon^2$.

$\mathbb Z^2$ is then a module over $\mathbb Z[M]$, and you are looking to describe the finite-index submodules of $\mathbb Z[M]$.

In the simplest case, $\mathbb Z^2$ is a (locally) free module over $\mathbb Z[M]$, and so you are describing the ideals of $\mathbb Z[M]$. In the ring of integers in a number field case, this has a particularly simple description, as products of prime ideals.

In the general order case, submodules are given by products of prime ideals away from those primes where the order $\mathbb Z[M]$ is not maximal or the module $\mathbb Z^2$ is not locally free, and there is additional complexity at those primes. Said another way, the simplest construction of such a subgroup is to take the product of $\mathbb Z^2$ with some ideal of the order $\mathbb Z[M]$, for example the intersection of $\mathbb Z[M]$ with an ideal of the ring of integers of the number field.

In the other cases there is a similarly concrete description.

If $v$ is not scalar, the ring $\mathbb Z[M]$ generated by $M$ has rank $2$ over $\mathbb Z$. It is therefore either an order in a number field, a finite-index subring of $\mathbb Z^2$, or $\mathbb Z[\epsilon]/\epsilon^2$.

$\mathbb Z^2$ is then a module over $\mathbb Z[M]$, and you are looking to describe the finite-index submodules of $\mathbb Z[M]$.

In the simplest case, $\mathbb Z^2$ is a (locally) free module over $\mathbb Z[M]$, and so you are describing the ideals of $\mathbb Z[M]$. In the ring of integers in a number field case, this has a particularly simple description, as products of prime ideals.

In the general order case, submodules are given by products of prime ideals away from those primes where the order $\mathbb Z[M]$ is not maximal or the module $\mathbb Z^2$ is not locally free, and there is additional complexity at those primes. Said another way, the simplest construction of such a subgroup is to take the product of $\mathbb Z^2$ with some ideal of the order $\mathbb Z[M]$, for example the intersection of $\mathbb Z[M]$ with an ideal of the ring of integers of the number field.

In the other cases there is a similarly concrete description.

Edit: Actually maybe I should say this a different way. Your idea of using the eigenvectors is a good one, but it's better to use the eigenvectors modulo $p$. Consider the characteristic polynomial of the element $M$, and its discriminant. If this discriminant is nonzero then there are infinitely many primes $p$ modulo which the discriminant is a nonzero square (quadratic reciprocity + Dirichlet's theorem). When the entries of $M$ are taken mod $p$, allowing us to view $M$ as a matrix over $\mathbb F_p$, it has two distinct eigenvalues and therefore two eigenvectors. The subgroup of vectors congruent mod $p$ to a multiple of one of these two eigenvectors is an index $p$ subgroup invariant under $M$.

If the discriminant is $0$ and $M$ is non-scalar, so $M$ has a single $2 \times 2$ Jordan block, then modulo all but finitely many primes $p$, $M$ will still have a single $2\times 2$ Jordan block, and you can take elements congruent mod $p$ to multiples of the unique eigenvector. Modulo the other primes, where $M$ becomes scalar, you can take multiples of any vector.