No caso de `Raiz` ser `NULL`, você está retornando lixo. Nesse caso é melhor retornar zero.

Também vejo que você está usando `||`, mas para verificar se o nó é folha, deveria ser `&&`.

Além disso, sugiro renomear `Raiz` para `raiz` e `somaFolha` para `soma_folha` de forma a ficar de acordo com o padrão do C.

E dá para simplificar bastante o código. Sugiro que ele fique assim:

    int soma_folha(struct NO **raiz) {
         if (raiz == NULL) return 0;
         if (raiz->esq == NULL && raiz->dir == NULL) return raiz->valor;
         return soma_folha(raiz->esq) + soma_folha(raiz->dir);
    }

Se você for fã do operador ternário, dá para simplificar um pouco mais:

    int soma_folha(struct NO **raiz) {
         return raiz == NULL ? 0
                 : raiz->esq == NULL && raiz->dir == NULL ? raiz->valor
                 : soma_folha(raiz->esq) + soma_folha(raiz->dir);
    }