So I’ve been looking and I can’t actually find anything to suggest that “deshita” is in any related to “desu.”

The masu form of verbs goes like this:
present: -masu
negative: -masen
past: -mashita
past negative: -masen deshita

Let’s assume when masu verbs were invented, desu didn’t exist. Why deshita? Well, the shita part indicates the past. The particle ‘de’ is used to indicate the time/location of an action, so deshita is sort of indicating that the preceding action occurred in the past.

But then what’s desu? No one knows for sure, but common belief is that it’s a shortened form of “de arimasu” (all the middle letters are removed). The de is, as far as I can tell, put there because historically it softened the phrase, making it sound more polite. That’s why desu is considered polite. So if you expand desu and look at all the ‘to be’ stuff, it looks like this:

present: de arimasu
negative: ja arimasen
past: de arimashita
past negative: ja arimasen deshita

So at this point, it’s beginning to look a lot like the masu form for aru, which is the “to be” verb. The only strange thing about it is the ja and the de. ‘ja’ is actually a shortening of ‘dewa’, and as far as I have found, dewa functions similarly to de in this context, but is even softer and even more polite. Perhaps this originated because speaking in the negative was considered more harsh and in need of more softening? I have no idea.

So the point of all this is that if you add desu to the end of ja arimasen, you’re actually saying ja arimasen de arimasu, which is nonsensical, where as if you put deshita at the end of ja arimasen, you’re just conjugating the masu form.