Hai dichiarato:
typedef struct node *list;
Quindi list corrisponde a node* (puntatore a nodo)
mentre list* corrisponde node** (puntatore a puntatore a nodo, detto anche puntatore doppio).
Quindi:
node* testa = (node*)malloc... ; //tipo list
node** ppnodo = &testa; //tipo list*
node* pnodo = *ppnodo; //ottengo un puntatore a node (list)
node* pnext = (*ppnodo) -> next; //ancora puntatore a node (list)
node nodo = **ppnodo; //ottengo un nodo
int a = (**ppnode).val;
int b = (*ppnode) -> val;
Partendo dalla variabile p, essendo un puntatore temporaneo al nodo successivo, lo dichiaro node* (list) e non node** (list*).
nella riga
if (l == NULL) return NULL; //caso base, lista vuota
Ma l (parametro di tipo list*) non è il puntatore al primo nodo, ma il puntatore al puntatore al primo nodo. Nel tuo caso l punta alla variabile nel main si chiama root, non a un nodo. Quindi se anche la lista è vuota, il puntatore alla testa è nullo, ma il puntatore al puntatore alla testa non è nullo (a meno chi tu non passi NULL come argomento).
p = (*l)->next;
Il puntatore al nodo successivo è di tipo list, non list*, per questo p va dichiarato list.
free(l);
Stessa cosa nel caso dell'if, per accedere al puntatore al nodo, devi usare *l, a meno che tu non voglia eliminare la variabile root.
(*l)->next = elimina((*l)->next, val);
Assegnazione sbagliata oltre che inutile. elimina restituisce node**, e tu la stai assegnando a un node*. Inoltre gli stai passando un node*, quando accetta un node**. Quindi gli devi dare l'indirizzo del puntatore al nodo successivo (cioè tipo node**), non un puntatore al nodo successivo (node*).
Spero di essere stato esauriente, magari qualcun altro lo sa spiegare meglio.