If the last cdr in a list is modified, then you need to propagate that change up to the front of the list during that modification, or check the whole list when you run `list?`. Either way, you pay linear time for it.
Only if the new value makes it no longer a list (or changes a dotted list into a real list). My hunch is that this would, in normal usages, work out to constant time (setf (cdr foo) ...) with the occasional (setf (cdr foo) atom) requiring the change in state to be propagated in linear time.
It's not only if the new cdr is an atom that the whole thing becomes a non-list. It remains a list if and only if the new cdr is a list. There are non-atom non-lists that could render it a non-list, but more disturbing is the case where the new cdr is a list until the modification is performed. If the cdr is modified to create a cycle, the the new cdr is a list right up until the point that modification is actually performed. The new cdr only ceases to be a list after the modification. So that's a really hairy situation. Note also that the cons cell being modified could belong to any number of lists or non-lists, not just one, so propagating through a change could be much worse than linear time in practice depending on what's being done. (Not to mention that propagating state the wrong direction through a chain of cons cells is itself a mess...)
Immutable cons cells eliminates all of this. If a cons cell is created with a list cdr, it will always be a list. If a cons cell is created with anything but a list as the cdr, it will never be a list. Very straight forward. You don't have to worry about linear time or worse propagations, and you don't need to anticipate what some other programmer down the line will consider "normal usage".
