Aparentemente, este é um problema conhecido com o OpenMP, uma biblioteca que fornece suporte multi-threading e é compilada no ImageMagick por padrão.
Para resolver isso, eu fiz o download e extraí as fontes do ImageMagick:
wget ftp://ftp.imagemagick.org:21/pub/ImageMagick/ImageMagick-6.9.1-2.tar.gz -O - | tar xzv
Em seguida, compilou assim:
cd ImageMagick-6.9.1-2
./configure --disable-openmp
make
sudo make install
para que minha versão seja assim:
$ /usr/local/bin/convert --version
Version: ImageMagick 6.9.1-2 Q16 x86_64 2015-05-24 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Features: DPC
Delegates (built-in): bzlib fftw fontconfig freetype jng jpeg lcms lqr lzma pangocairo png tiff webp x xml zlib
e finalmente funcionou - já não congela e imediatamente produz a saída que eu quero.