Hola, disculpame si no te respondì antes.
Mira, hace tiempo atrás tuve mas o menos el mismo problema que vos (te doy del tu ), y me acuerdo que en el database habían 2/3 tablas que habían crecido muchísimo y una vez vaciadas, prestashop volaba.
Te dejo el link https://www.prestashop.com/forums/topic/385659-ps-connection/?do=findComment&comment=1887960 a este post, mira la imagen y son esas las tablas que habría que vaciar. Solo que justamente esas se refieren a las estadísticas de las conexiones a tu tienda.
Lo que podrías probar antes de vaciarlas es:
1) Instalar el modulo pscleaner, estando atento a no borrar cosas útiles
2) Si tenes pensado pasar a la version 1.6.1.x, podrías crearte un ambiente LAMP en una compu local, bajar la tienda y database (reproduciendo en local la tienda) y ver como va después de la actualización.
O si no te queres complicar mucho la vida, duplicas la tienda en tu hosting, duplicando también el database e haciendo la actualización en la tienda de prueba.
/*EDIT*/
Vos por casualidad usas también las reglas de descuento?
Para ver cual es la tabla mas grande, te conviene entrare en el phpmyadmin y ordenar las tablas por el espacio ocupado y asì vas a ver si hay alguna tabla enorme. Yo me encontré una vez con un par de tablas de algunos GB