It is because of iCloud. When I factory restore my phone and set up as new. my call logs come back so I assume it's saved in iCloud for apparent reason.
Same goes for my wife's 6S Plus, which I just got her yesterday. We set it up as a New device, and just checked her call logs, and looks like the call logs transferred over from her 4S. So clearly it is saved in iCloud.