Eliminando muchas referencias a muchas en Mongoose

Estás en el camino correcto para usar 'remove' middleware para esto. En la función de middleware, this es la instancia de grupo que se está eliminando y puede acceder a los otros modelos a través de su model método. Entonces puedes hacer algo como:

GroupSchema.pre('remove', function(next){
    this.model('User').update(
        {_id: {$in: this.users}}, 
        {$pull: {groups: this._id}}, 
        {multi: true},
        next
    );
});

O si desea admitir casos en los que los users el campo en su instancia de grupo puede no estar completo, podría hacer:

GroupSchema.pre('remove', function(next){
    this.model('User').update(
        {groups: this._id}, 
        {$pull: {groups: this._id}}, 
        {multi: true},
        next
    );
});

Pero como señala WiredPrairie, para esta opción querrás un índice en groups para un buen rendimiento.