Suppose $G = (V,E)$ is a directed graph. For sets $A$ and $B$ of vertices of $G$, let $d(A,B) = |(A \times B) \cap E| / (|A||B|)$ denote the edge density between $A$ and $B$, and say that the pair $A,B$ is $\epsilon$-regular if $$ |d(X,Y) - d(A,B)| \lt \epsilon $$ whenever $X \subseteq A, Y \subseteq B$, $X$ contains more than an $\epsilon$-fraction of the vertices of $A$, and $Y$ contains more than an $\epsilon$-fraction of the vertices of $B$. An equipartition is a partition with the sizes of blocks of the partition differing pairwise by at most 1.
Szemerédi's Regularity Lemma can then be stated as:
For any $\epsilon > 0$, there exists $M(\epsilon)$ such that for every graph $G=(V,E)$ there is some $k\le M(\epsilon)$ and an equipartition $V = V_1 \cup \ldots \cup V_k$ in which each block $V_i$ contains at most $\lceil \epsilon |V|\rceil$ vertices, and having the property that for all but at most $\epsilon k^2$ of the pairs $(i,j)$, the pair $V_i, V_j$ is $\epsilon$-regular.
Do we have any bounds or asymptotics for how $M(\epsilon)$ behaves as a function of $\epsilon$?
I vaguely recall having read a comment that $M(\epsilon)$ is likely to be extremely large, making the Regularity Lemma only useful for truly large graphs. But I have not been able to find this assessment again, so a pointer would be appreciated. (I did check Terence Tao's exposition again, and some of the more obvious references.)