Suppose that $M$ is a compact irreducible 3-manifold.

1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. If $M$ is a closed hyperbolic 3-manifold, then, of course, you get a linear estimate.

From the practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation. However, in principle, techniques for such estimates are available once you computed a Haken hierarchy (if $M$ is Haken). In general, this is an open problem how to extract geometric information about hyperbolic structure from a triangulation (besides estimating the hyperbolic volume), although in the last 10-15 years there was some progress in this direction.

2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in (correction) $O(n^2)$-time: You just multiply integer matrices.

3. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.

Thus, the answer to your question is "at most quadratic and in some cases linear." The fact that the estimate is always quadratic suggests that there is a uniform proof of such a quadratic bound. I have no idea how this could/would work.

Some references:

Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P., Word processing in groups, Boston, MA etc.: Jones and Bartlett Publishers. xi, 330 p. (1992). ZBL0764.20017.

Aschenbrenner, Matthias; Friedl, Stefan; Wilton, Henry, 3-manifold groups, EMS Series of Lectures in Mathematics. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-154-5/pbk). xiv, 215 p. (2015). ZBL1326.57001.

Suppose that $M$ is a compact irreducible 3-manifold.

1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. If $M$ is a closed hyperbolic 3-manifold, then, of course, you get a linear estimate.

From the practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation. However, in principle, techniques for such estimates are available once you computed a Haken hierarchy (if $M$ is Haken). In general, this is an open problem how to extract geometric information about hyperbolic structure from a triangulation (besides estimating the hyperbolic volume), although in the last 10-15 years there was some progress in this direction.

2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in (correction) $O(n^2)$-time: You just multiply integer matrices.

3. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.

Thus, the answer to your question is "at most quadratic and in some cases linear." The fact that the estimate is always quadratic suggests that there is a uniform proof of such a quadratic bound. I have no idea how this could/would work, apart from proving (Thurston's?) conjecture that fundamental groups of all compact 3-manifolds embed in $SL(N,Z)$ for some nonuniform $N$. The latter is known in "most" but not all cases.

Some references:

Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P., Word processing in groups, Boston, MA etc.: Jones and Bartlett Publishers. xi, 330 p. (1992). ZBL0764.20017.

Aschenbrenner, Matthias; Friedl, Stefan; Wilton, Henry, 3-manifold groups, EMS Series of Lectures in Mathematics. Zürich: European Mathematical Society (EMS) (ISBN 978-3-03719-154-5/pbk). xiv, 215 p. (2015). ZBL1326.57001.

1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. (One can actually do better, see below.) From practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation.

2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in $O(n)$-time: You just multiply integer matrices.

3. Assume that $M$ is a compact irreducible 3-manifold. Unless $M$ is a graph-manifold with empty boundary, it is known that $G=\pi_1(M)$ embeds in some $SL(N, Z)$ (with $N$ depending on $M$). Hence, the WP in $G$ is again decidable in $O(n)$-time. The same argument works for some classes graph-manifolds but the problem (afaik, but I might have missed some recent developments) is currently open. But constructing such matrix representations is totally nonpractical.

4. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.

Thus, the answer to your question is "at most quadratic and in most cases linear."

1. Assume that $M$ is neither a Nil nor a Sol-manifold. Then $G=\pi_1(M)$ is automatic, which implies that $G$ has quadratic Dehn function and the word problem in $G$ is decidable in $O(n^2)$-time. If $M$ is a closed hyperbolic 3-manifold, then, of course, you get a linear estimate.

From the practical standpoint, finding an automatic structure on $G$ if $M$ is just given by its triangulation is a hard task. Even in the case when $M$ is a closed hyperbolic 3-manifold given by its triangulation, I do not think there are known explicit estimates of hyperbolicity constant for $G=\pi_1(M)$ (with generating set, say, given by the triangulation) in terms of the triangulation. However, in principle, techniques for such estimates are available once you computed a Haken hierarchy (if $M$ is Haken). In general, this is an open problem how to extract geometric information about hyperbolic structure from a triangulation (besides estimating the hyperbolic volume), although in the last 10-15 years there was some progress in this direction.

2. If $M$ is a Nil or a Sol-manifold, the group $G=\pi_1(M)$ embeds in $SL(3, Z)$. Hence, the WP in $G$ is decidable in (correction) $O(n^2)$-time: You just multiply integer matrices.

3. In the case of reducible oriented 3-manifolds, the fundamental group splits as a free product of fundamental groups of irreducible components and you obtain the same estimates on complexity of the WP as above.

Thus, the answer to your question is "at most quadratic and in some cases linear." The fact that the estimate is always quadratic suggests that there is a uniform proof of such a quadratic bound. I have no idea how this could/would work.