When I try and compile ImageMagick using the args --with-perl I get the error cannot find -lperl (After researching, I'm assuming this is libperl.so its after).

Here is what I would do :) install precompiled ImageMagick say yum install ImageMagick or whatever ubuntu does

Then do cpanp -z Image::Magick and like the readme says edit Makefile.PL for defaults for LIBS & INC & CCFLAGS params that we later pass to Writemakefile