Handle an error.

I suggest to use a list instead of a tuple. You can fill it at the single pass and convert to a tuple at end.

if (!new_bases) {
    new_bases = PyList_New(i);
    if (!new_bases) {
        goto error;
    }
    // copy i items to new_bases
}
if (_PyList_Extend(new_bases, new_base) < 0) {
    goto error;
}

I think the code would look simpler if pass nargs-2 and args+2. Or passing just bases may be enough.

Needed a space before {.

Just

Py_XDECREF(old_bases);

This is not really possible, since this code is also executed on success, and in this case if there were no conversion, then bases should be DECREFed exactly once.

The code would look simpler if set the original bases to orig_bases.

orig_bases = _PyStack_AsTupleSlice(...);
if (orig_bases == NULL)
    return NULL;
bases = update_bases(...);
if (bases == NULL) {
    Py_DECREF(orig_bases);
    return NULL;
}

if (bases != orig_bases) {

modified_bases is not needed.

meth is NULL here.

I suggest to swap branches and move the success branch to upper level. I think this will make the code clearer.

if (!PyTuple_Check(new_base)) {
    ...
    goto error;
}
if (!new_bases) {
    ...

It would look clearer if make an assignment on a separate line.

Is this comment outdated?

For performance try to add a separate fast loop for non-generic types.

for (i = 0; i < nargs && PyType_Check(args[i]); i++) {
}
if (i == nargs) {
    return bases;
}
new_bases = PyList_New(i);
...
for (; i < nargs; i++) {

This doesn't give any visible difference, so I will just keep the single loop (As I mentioned before, a more careful benchmark showed that it is already good).

Check for error.

This looks confusing. Add a comment to this non-obvious code.

Alternatively you can use a public PyList_SetSlice instead of _PyList_Extend if you prefer.

j = PyList_GET_SIZE(new_bases);
if (PyList_SetSlice(new_bases, j, j, new_base) < 0) {
    goto error;
}

Add the const qualifier. See bpo-32240.

It is more common to add a space before * instead of after it.

This is just my personal preference, but I prefer to add an empty line after return and before a label (closing brace can replace an empty line). This make the code cleaner to me.