An alternative to the tail memmove would just be to incorporate it in the main loop; something like (untested):

for(i=0; i<slicelength; i++){
    size_t target = start + i * (step - 1);
    size_t source = start + i * step + 1;
    size_t source_end = i < slicelength - 1 ? source + step - 1
                                            : self->ob_size;
    garbage[i] = PyList_GET_ITEM(self, start + i * step);
    assert(source_end <= self->ob_size);
    memmove(&self->ob_item[target], &self->ob_item[source],
        (source_end - source) * sizeof(PyObject *));
}

I think this also makes it more obvious what's going on - at the moment the code smells a bit funny, even with your new comment.

Otherwise, the change looks good.