I want to calculate the Hilbert series $P(M,t) = \sum_{i\in\mathbb{Z}} (\operatorname{rank}_k M_i)t^i$ for the polynomial ring $R = k[x^4, x^3y, xy^3, y^4]$ where $\deg(x^4) = 1, \deg(y^4)=1$.
Then I tried a couple cases, like
\begin{align} M_0 & = \langle 1\rangle, \\ M_1 & = \langle x^4, y^4, x^3y, xy^3\rangle, \\ M_2 & = \langle (x^4)^2, (y^4)^2, (x^3y)(xy^3) \rangle,\\ M_3 & = \langle(x^4)^3, (y^4)^3, (x^3y)^2(xy^3), (x^3y)(xy^3)^2, (x^3y)(xy^3)y^4, x^4(x^3y)(xy^3)\rangle,\ldots \end{align}
So $\operatorname{rank}(M_0) = 1, \operatorname{rank}(M_1) = 4, \operatorname{rank}(M_2)=3, \operatorname{rank}(M_3) = 6$.
I am not sure my method is correct, for example I am not sure if $x^3y, xy^3$ count as degree 1 elements, also I am not sure how to conclude what the Hilbert series should be...
Your initial approach of writing down bases for each graded piece as a vector space is a good no-tech way to start on the problem, but you've made some errors. (You are correct that $x^3y$ and $xy^3$ should be in degree one: $(x^3y)^4=(x^4)^3y^4$.)
At this point, our function appears have stabilized as linear, and we would conjecture that the Hilbert polynomial is $4x+1$. In order to prove this, one could prove the claim that you can build all the monomials of the form $x^ay^{4b-a}$ for $b>1$ out of products of $x^4,y^4,x^3y,xy^3$.
Alternatively, you can pursue the hint from the comments. If you can write your module as quotient of a polynomial ring, you can take a free resolution of it, use the fact that Hilbert polynomials play nicely with exact sequences, and then profit. See this answer for details about how that ought to work.