Just an addition since I had issues with the python script (and several other solutions): for me mutool worked great. It's a simple and small addition shipped with the elegant mupdf reader. So you can try:
mutool poster -y 2 input.pdf output.pdf
For horizontal splits, replace y with x. And you can, of course, combine the two for more complex solutions.
Really happy to have found this (after years of daily mupdf usage :)
Installing mupdf and mutool from source
(mutool comes shipped with mupdf starting from version 1.4: http://www.mupdf.com/news)
Installing mupdf and mutool from source:
wget http://www.mupdf.com/downloads/mupdf-1.8-source.tar.gz
tar -xvf mupdf-1.8-source.tar.gz
cd mupdf-1.8-source
sudo make prefix=/usr/local install
Or go to the downloads page to find a newer version.
Installing mutool from a Linux distribution package
On Debian, the package containing mutool is mupdf-tools:
apt-get install mupdf-tools
