mkdir e rmdir criam e removem diretórios. pushd e popd são apenas uma interface para uma pilha de locais. Você pode armazenar um local na pilha ou recuperá-lo. A pilha não se importa se a localização nela armazenada realmente existe.
Em outras palavras, se você armazenar um diretório por pushd e removê-lo, ele permanecerá na pilha. Chamar popd causaria um erro e a pilha não mudaria.