It's gradually coming back to me. The Haskell Complex type doesn't work particularly nicely as an integer, plus the definition of division is more like "scale", so I just went with my own type.

Then I forgot which of div and quot I should use, and kept getting nearly the right answer :/

import Data.Ix  

data CNum = CNum !Integer !Integer  

instance Show CNum where  
  show (CNum x y) = "[" ++ show x ++ "," ++ show y ++ "]"  

cadd, cmul, cdiv :: CNum -> CNum -> CNum  
(CNum x1 y1) `cadd` (CNum x2 y2) = CNum (x1 + x2) (y1 + y2)  
(CNum x1 y1) `cmul` (CNum x2 y2) = CNum (x1 * x2 - y1 * y2) (x1 * y2 + y1 * x2)  
(CNum x1 y1) `cdiv` (CNum x2 y2) = CNum (x1 `quot` x2) (y1 `quot` y2)  

part1 a = iterate op (CNum 0 0) !! 3  
  where  
    op x = ((x `cmul` x) `cdiv` CNum 10 10) `cadd` a  

countEngraved = length . filter engrave  
  where  
    engrave p =  
      let rs = take 100 $ tail $ iterate (op p) (CNum 0 0)  
       in all (\(CNum x y) -> abs x <= 1000000 && abs y <= 1000000) rs  
    op p r = ((r `cmul` r) `cdiv` CNum 100000 100000) `cadd` p  

part2 a =  
  countEngraved  
    . map (\(y, x) -> a `cadd` CNum (x * 10) (y * 10))  
    $ range ((0, 0), (100, 100))  

part3 a =  
  countEngraved  
    . map (\(y, x) -> a `cadd` CNum x y)  
    $ range ((0, 0), (1000, 1000))  

main = do  
  print $ part1 $ CNum 164 56  
  print $ part2 $ CNum (-21723) 67997  
  print $ part3 $ CNum (-21723) 67997