I hit the same exact error as in here: 'sqlcmd' is not recognized at CreateShardApplicationDatabaseServerLoginSqlCmd step
I tried the suggestion there to install the 2 modules required. The environment path was also present when I check.
Still it does not work.
The only reason I can think of is the version of modules required for Windows Server 2016 might be different.
Please share your ideas if you have similar issues