I find it hard to imagine how "need to count" can have more than the most trivial of impacts on the efficiency of a mutex.

See for yourself. It's not just time but also space efficiency.

Here is perl's current implementation of recursive locking

typedef struct {
    perl_mutex          mutex;
    PerlInterpreter    *owner;
    I32                 locks;
    perl_cond           cond;
} recursive_lock_t;

void
recursive_lock_acquire(pTHX_ recursive_lock_t *lock, char *file, int l
+ine)
{
    assert(aTHX);
    MUTEX_LOCK(&lock->mutex);
    if (lock->owner == aTHX) {
        lock->locks++;
    } else {
        while (lock->owner) {
          COND_WAIT(&lock->cond,&lock->mutex);
        }
        lock->locks = 1;
        lock->owner = aTHX;
    }
    MUTEX_UNLOCK(&lock->mutex);
    SAVEDESTRUCTOR_X(recursive_lock_release,lock);
}
[download]

And that lot -- a mutex and owner, a locks count and a condition variable is built on top of this lot:

115: typedef union
116: {
117:   struct
118:   {
119:     int __lock;
120:     unsigned int __futex;
121:     __extension__ unsigned long long int __total_seq;
122:     __extension__ unsigned long long int __wakeup_seq;
123:     __extension__ unsigned long long int __woken_seq;
124:     void *__mutex;
125:     unsigned int __nwaiters;
126:     unsigned int __broadcast_seq;
127:   } __data;
128:   char __size[__SIZEOF_PTHREAD_COND_T];
129:   __extension__ long long int __align;
130: } pthread_cond_t;
[download]

And this:

76: typedef union
77: {
78:   struct __pthread_mutex_s
79:   {
80:     int __lock;
81:     unsigned int __count;
82:     int __owner;
83: #if __WORDSIZE == 64
84:     unsigned int __nusers;
85: #endif
86:     /* KIND must stay at this position in the structure to maintai
+n
87:        binary compatibility.  */
88:     int __kind;
89: #if __WORDSIZE == 64
90:     int __spins;
91:     __pthread_list_t __list;
92: # define __PTHREAD_MUTEX_HAVE_PREV      1
93: #else
94:     unsigned int __nusers;
95:     __extension__ union
96:     {
97:       int __spins;
98:       __pthread_slist_t __list;
99:     };
100: #endif
101:   } __data;
102:   char __size[__SIZEOF_PTHREAD_MUTEX_T];
103:   long int __align;
104: } pthread_mutex_t;
105:
[download]

Which, when you realise that a non-recursive lock can be built atop a single bit, starts to look just a little indulgent.