In short: Yes.
Or rather, no, but your question hints to a fundamental conceptual misdesign, so... yes.
It's actually "no" because lightweight locks which take very few resources, and few handles (or none at all!) can be easily implemented. For an ultra-low congestion situation with short lock durations such as "a dozen threads at most" vs. "a million lockable things", a spinlock is perfectly suitable.
If you are afraid of spinning (shouldn't be in this situation -- spinning is bad if, and only if there is contention), locks which can block and consume a single handle for the entire process can be built around
NtWaitForKeyedEvent on Windows, an locks which block and need no handle at all can be built around
WaitOnAddress on Windows >= 8, or
futex on Linux >= 2.6 systems. That's ultra-lightweight, and you can literally have millions of them (though you probably do not actually want to have that many).
Note that millions of concurrent users is not millions of threads running on the server. Generally, in terms of concurrent users, you might want to think of "10,000 to 50,000" rather than "million" anyway, since the former is pretty unrealistic unless you have a whole farm of servers. Which is... uh... a different beast altogether. Either way, you don't need more than a handful of concurrent threads for these.
Also, millions of users are not millions of singular, distinct, lockable collections (or things, whatever) on the server. Not normally, at least. Normally, there will be something like a database containing them all (not saying you couldn't do it differently, it's just very unusual). Nitpick: Yes, row-level locking is a feature that some databases do implement, so yeah, you can have millions of locks either way, without knowing.
Depending on what the frequencies of reads versus updates are, you may consider techniques such as read-copy-update which avoid locking, too. RCU doesn't need a handle. You do it either via an extra pointer indirection and atomic reads/writes on the pointer, or by doubly incrementing a counter (atomically) and restarting the reader if a mid-way modification was found (i.e. if the counter is odd the second time you look at it). No blocking, no locks, no handles. Depending on the access pattern, this strategy can be big win.
There exist different strategies for handling large number of clients, one would be to have one multiplexer thread for the network stuff (possibly a few). For that, functions like
kqueue come to mind, depending on which operating system(s) you target.
Seeing how C# often (but not necessarily) implies Windows,
GetQueuedCompletionStatus looks like what you'd want to use (maybe C# even has a higher-level multiplexing functionality built on top of that available too, I wouldn't know, not using C#). For that, usually more than just one thread is used (can do half a dozen without caring much how many exactly, the function blocks/wakes them as needed), but you don't need an awful lot of them. One will probably do just fine, too. With e.g.
epoll, using a single multiplexer thread is the normal thing (although you can do something different). Works perfectly well, no performance problems.
Last, a pool of workers (roughly the number of CPU cores) doing, well, whatever heavy lifting must be done in addition, and concurrent queues of some sort to communicate between them and I/O. What you use exactly (locked queue, lockfree/waitfree queue, disruptor, busy spinning or yielding, or even blocking, whatever) depends on the exact situation. Each has different strenghts and weaknesses. Note that locked concurrent structures are not in any way as abysmal as you would think. Except under hefty congestion, they're actually quite good (and dead simple to get right whereas lockfree stuff is nightmarish).
If you happen to use UDP rather than TCP (but be sure you understand the implications, notably you have to do all the reliability stuff yourself), a single dedicated thread can do all the sends in a simple blocking, one-by-one fashion. That is the simplest way, total no-brainer, 100% portable, and suffices to physically saturate the ethernet cable, and it doesn't cause needless packet loss due to threads pushing stuff to the network stack concurrently.
You also do not strictly need to wait for readiness/completion either if you use UDP. Plain, ordinary blocking reads from one or several workers will do perfectly fine, and you can hardly press more performance out of it either way (except when using special "cheat" functions like
recvmmmsg that grab a dozen datagrams in one go).
If no heavy processing is needed, and latency is not paramount (so messages possibly being delayed half a second is no issue) you can probably do a server that handles a few thousand concurrent connections single-threaded, too. The above multiplexing APIs have no real trouble handling that, nor does the network stack.