Is it possible that "Chinese remainder theorem" was used by the Chinese military? Who knows. But we know that the proliferation of Chinese generals and soldiers in connection with it comes from late fables. The original source of the "theorem" is Sunzi Suanjing, which has nothing to say about counting soldiers. The problem is stated thus:
"There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?"
The book is dated to 3-5th century AD, and nothing is known about the author, but the name Sun Zi is spelled the same way as Sun Tzu, the famous Chinese general who wrote The Art of War. That Sun Tzu lived c. 500 BC does not stop some modern enthusiasts from attributing Sunzi Suanjing to him anyway.
Another Chinese general associated with the theorem is Han Xin, who lived c. 200 BC. A Singaporean blogger tells an "amazing" story of him and his army of 1500 soldiers estimated 400-500 of which died in a battle:
"When the soldiers stood 3 in a row, there were 2 soldiers left over. When they lined up 5 in a row, there were 4 soldiers left over. When they lined up 7 in a row, there were 6 soldiers left over. Han Xin immediately said, “There are 1049 soldiers".
No source for this amazing story is given (it is repeated or mentioned in many other places though), but from Volkov's paper in From China to Paris, p.402 we learn that Han Xin dian bing (Han Xin's way of counting soldiers) dates to 13th century AD, when Cheng Dawei mentions it as a name of a rhymed stanza. Qin wang an dian bing (Prince of Qin's method of secretly counting soldiers) occurs somewhat earlier in Yang Hui's Xiangjie Jiuzhang Suanfa (c. 1265 AD), better known for magic squares, magic circles and Yang Hui's (a.k.a. Pascal's) triangle.
This explosion of popularizations seems to follow Qin Jiushao's Shùshū Jiǔzhāng (c.1245 AD), which presented a complete solution to the remainder systems of equations with multiple examples. As usual with anecdotes, memorable illustrations were then invented and ascribed to famous historical figures, acquiring more and more details over the subsequent centuries. The name "Chinese Remainder Theorem" comes from 19th century Europe, see What is the history of the name “Chinese remainder theorem”?
For a more mathematically focused history see Kangsheng's Historical development of the Chinese remainder theorem.