How to connect to SQL Server using sqlcmd on Linux?
With the help of Dan Guzman's comment I got the connection working using a port. 

I had a Windows machine with SQL Management Studio connected to the database in question, and used:

netstat -abn


Then I searched for ssms.exe for the connection details:

TCP    192.168.0.31:50777     192.168.0.78:49399     ESTABLISHED [Ssms.exe]


Alternatively log into the database server and look at the ports used by the instance in SQL Server Configuration Manager (SQL Server Network Configuration > Protocols for INSTANCENAME > TCP/IP > Properties > IPAll TCP Dynamic Ports). 

The following then both worked:

sqlcmd -S 192.168.0.78,49399 -U User -P pwd -d DatabaseName -Q "SELECT TOP 5 Id FROM dbo.MyTable;"
sqlcmd -S SERVERNAME,49399 -U User -P pwd -d DatabaseName -Q "SELECT TOP 5 Id FROM dbo.MyTable;"