Este mensaje aparece cuando no está instalado la utilidad sqlcmd , o no cuenta con sql server instalado. O también puede ser que esté instalado y no este registrado en la variable de entorno.
 Para trabajar con la utilidad sqlcmd en un equipo que no tiene sql server instalado es necesario descargar e instalar la utilidad.
Descargar SQLCMD.
https://www.microsoft.com/en-us/download/details.aspx?id=53591
Es necesario instalar lo siguiente:
Windows Installer y el Driver ODBC de SQL Server
- Windows Installer es una Aplicación para la instalación y configuración de los programas en el equipo. 
 Descargar: https://www.microsoft.com/en-us/download/details.aspx?id=8483
- Microsoft ODBC Driver 13.1 for SQL Server, es un estándar de acceso a bases de datos que utilizan los sistemas Microsoft. Las siglas significan Open DataBase Connectivity. A través de ODBC, en un sistema Windows se puede conectar con cualquier base de datos.
 Descargar: http://go.microsoft.com/fwlink/?LinkId=825608
 
Observación:
Si una vez realizado la instalación  sigue saliendo: "Sqlcmd no se reconoce como un comando interno o externo".  Se debe verificar las variables de entorno del sistema. Mi PC -> botón derecho -> Propiedades -> Opciones Avanzadas -> Variables de Entorno, Variables de Sistema, Variable Path 
 tiene que aparecer lo siguiente:  %SystemRoot%\system32;%SystemRoot%;%SystemRoot%\system32\WBEM 
 
 Si no aparece, editarlo y modificarlo por ese valor y por ultimo reinicia sistema.
Imágenes de referencia:

Ventana de Propiedades del Sistema -> Opciones avanzadas 

Ventana de variables de entorno.

Ventana de modificación de las variables de entorno.