Probe tambien sacando $pagina-1 de las comillas a ver si era que en vez de pedirle que sume le estaba pidiendo que lo escriba pero tampoco lo pude solucionar.
Dejo como probe:
Código PHP:
echo "<a href='paginacionprueba.php?pagina=".$pagina-1."'>$pagina-1</a>";