Bueno una forma de que elimine todos es que cuando la persona seleccione todos, tu verifiques si los tiene todos seleccionado para eliminar y si es asi creas un if y dentro que haya esto
Código PHP:
if(CONDICION_QUE_VERIFICA_SI_TODOS_ESTAN_SELECCIONADOS_PARA_ELIMINAR){
$_SESSION['carrito'] = "";
}