Your function is singly recursive, so if we ensure it also is tail recursive we can maintain its memory size. The trick is not to produce more outstanding operations. The guards make the function strict in y, so we know that isn't some arbitrary tree of calculations waiting to happen. But x varies with call depth and isn't required until we produce the return value, and the return value has three cases: constant, tail recursive, and recursive with two operations (* and mod) outside the call. Those operations will go on some sort of call stack.
Solving this is probably a two step operation: First, make the function wholly tail recursive. Second, make it strict, such that it evaluates eagerly rather than building more and more complex expressions.
Tail recursive variant:
modExp :: Integer -> Integer -> Integer -> Integer
modExp x y m = modExp' x y m 1
where
modExp' x y m acc
| y == 0 = acc
| y `mod` 2 == 0 = modExp' ((x ^ 2) `mod` m) (y `div` 2) m acc
| otherwise = modExp' x (y - 1) m (x * acc `mod` m)
It may be useful in some cases to enforce strictness in x and acc as well. That can be done with seq:
modExp :: Integer -> Integer -> Integer -> Integer
modExp x y m = modExp' x y m 1
where
modExp' x y m acc
| y == 0 = acc
| y `mod` 2 == 0 = let x' = (x ^ 2) `mod` m
y' = y `div` 2
in x' `seq` modExp' x' y' m acc
| otherwise = let acc' = x * acc `mod` m
in acc' `seq` modExp' x (y - 1) m acc'
A slightly simpler variant could apply seq to x or acc themselves, which in principle might leave one layer of calculation unfinished, but no more. Either way enforces constant space.
Unfortunately I didn't reproduce your stack overflow using ghc 7.10.3, so I'm not quite certain which lengths will prove necessary.
