Potrebbe essere che header location ti rimandi alla nuova pagina in modo continuativo cioe' senza terminare formalmente la pagina corrente con la chiusura del tag php.

La sessione viene scritta al momento della chiusura della pagina (mi son fatto una cultura per una malf...) e quindi e' probabile che questa scrittura non avvenga.

Prova a forzare la chiusura prima dell'header location...
codice:
#Cancellazione Sessione shop

unset($_SESSION['shop']);

session_write_close();

#Reindirizzamento alla gestione prodotti

header("Location: carrello.php");