It's not a single solution and I suspect that's a big part of the cause of slowness.
As noted already. one solution can be found quickly like so.
mM1 = {{0, 1, 0, 0}, {-4, 0, 0, 0}, {0, 0, 0, 1}, {0, 0, -4, 0}};
mM2 = {{0, 1, 4, 0}, {-4, 0, 0, -4}, {0, 0, 0, 1}, {0, 0, -4, 0}};
mM = Array[x, {4, 4}];
sol1 = First[
mM /. FindInstance[Flatten[{mM1 . mM == mM . mM2, Det[mM] == 1}],
Flatten[mM], Integers]]
(* Out[30]= {{0, 0, 1, 0}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, 1, 4, 0}} *)
We can get another by ignoring the determinant constraint, solving over the integers, and then imposing it on the resulting parametrized solution.
InputForm[
Timing[soln =
Solve[Flatten[{mM1 . mM == mM . mM2}], Flatten[mM], Integers]]]
(* Out[32]//InputForm=
{0.008802, {{x[1, 1] -> ConditionalExpression[C[4],
Element[C[3] | C[4], Integers]],
x[1, 2] -> ConditionalExpression[-C[2],
Element[C[1] | C[2], Integers]],
x[1, 3] -> ConditionalExpression[C[1], Element[C[1] | C[2],
Integers]], x[1, 4] -> ConditionalExpression[C[3],
Element[C[3] | C[4], Integers]],
x[2, 1] -> ConditionalExpression[4*C[2],
Element[C[1] | C[2], Integers]],
x[2, 2] -> ConditionalExpression[C[4], Element[C[3] | C[4],
Integers]], x[2, 3] -> ConditionalExpression[
-4*C[3] + 4*C[4], Element[C[3] | C[4], Integers]],
x[2, 4] -> ConditionalExpression[C[1] + 4*C[2],
Element[C[1] | C[2], Integers]],
x[3, 1] -> ConditionalExpression[C[8], Element[C[7] | C[8],
Integers]], x[3, 2] -> ConditionalExpression[-C[6],
Element[C[5] | C[6], Integers]],
x[3, 3] -> ConditionalExpression[C[5], Element[C[5] | C[6],
Integers]], x[3, 4] -> ConditionalExpression[C[7],
Element[C[7] | C[8], Integers]],
x[4, 1] -> ConditionalExpression[4*C[6],
Element[C[5] | C[6], Integers]],
x[4, 2] -> ConditionalExpression[C[8], Element[C[7] | C[8],
Integers]], x[4, 3] -> ConditionalExpression[
-4*C[7] + 4*C[8], Element[C[7] | C[8], Integers]],
x[4, 4] -> ConditionalExpression[C[5] + 4*C[6],
Element[C[5] | C[6], Integers]]}}} *)
dd = First[Det[mM /. soln[[1]]]];
dvars = Variables[dd];
d1 = FindInstance[dd == 1, dvars, Integers];
(* {{C[2] -> 0, C[5] -> 1, C[4] -> 1, C[1] -> 0, C[6] -> 0, C[3] -> 0,
C[7] -> 0, C[8] -> 0}} *)
This does give a different (albeit quite similar) solution.
sol2 = First[mM /. (soln /. d1)]
(* Out[33]= {{{1, 0, 0, 0}, {0, 1, 4, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}} *)
Again, asking for more than one appears to get into a hang situation.