(Warning: I do not know phonetics in general, and I do not speak Mandarin. I am writing this answer while consulting Wikipedia. Although I am trying my best to write an accurate answer, you should take it with a grain of salt, especially with my use of technical terms and with statements about Mandarin.)
My question is, are the two sh's completely indistinguishable to Japanese ears?
Completely? Probably no. But they are almost indistinguishable to most native speakers of Japanese.
In both English and Japanese, there is only one phoneme realized by voiceless postalveolar fricatives (the same holds for voiced postalveolar fricatives):
(The primary difference between these two consonants is the shape of the tongue.)
Therefore, most native speakers of English are not trained to distinguish different postalveolar fricatives, and they pronounce the consonant of しゃ, しゅ, しぇ, しょ as [ʃ] when they speak Japanese. This does not cause a problem for comprehension because we (native speakers of Japanese) are also not trained to distinguish different postalveolar fricatives. We probably notice something different in their pronunciation and recognize it as “Japanese with English accents,” but that’s all. Probably the same thing happens when native speakers of Japanese speak English.
(I wrote “しゃ, しゅ, しぇ, しょ” above. What happens when a native speaker of English pronounces し in Japanese? I cannot tell from my experience, but if he/she gets the vowel [i] in Japanese right, probably he/she will necessarily pronounce [ʃ] in a more palatalized way, resulting in [ɕ], even if he/she is not aware of it.)
This situation may look strange to you if [ʃ] and [ɕ] belong to distinct phonemes in your native tongue: how can anyone be unaware of the obvious difference between [ʃ] and [ɕ]? But the notion of “similar sounds” is surprisingly different from one language to another. For example, many native speakers of Japanese have trouble distinguishing [s] and [θ] when we speak English, and native speakers of English might wonder how anyone can be unaware of the obvious difference between [s] and [θ]. (I guess the same example applies to native speakers of Mandarin.) As another example, many native speakers of English have trouble distinguishing きょう (今日) and きよう (器用) when they speak Japanese, and native speakers of Japanese might wonder how anyone can be unaware of the obvious difference between them.
By the way, “sh” in Mandarin is not [ʃ] (“sh” in English), either. According to Wikipedia, it is retroflex fricative [ʂ], and therefore it has yet another tongue shape. If you do not notice the difference between Mandarin [ʂ] and English [ʃ], that is probably because of the same reason why native speakers of English and native speakers of Japanese do not notice the difference between English [ʃ] and Japanese [ɕ].
