Identifying the problem

This issue is widely reported on Apple support and individual app support forums all over the Internet. I believe it has little to do with the amount of free space on your iOS device, but instead iTunes is ambiguously informing you concerning the amount of free space on your computer's hard drive. Though the support article I link is concerning backups failing to restore through iTunes, it does describe the issue.

What is happening is iTunes has determined there is not enough free space on your hard drive to backup the iOS device once that file syncs over. The reason for this is that by default, iOS device backups include all apps and all documents those apps store (including your large mkv file), which is why when you sync, the longest process is usually the first one, the notorious backup process, which occurs at every sync.

Solutions

disable full iTunes backups

Changing the behavior of iTunes backups to ignore the documents stored on your iOS device is one solution to your issue.

to disable full iTunes backups on OS X, enter this command in /Applications/Utilities/Terminal.app :

 defaults write com.apple.iTunes DeviceBackupsDisabled -bool true

to reenable the full iTunes backups switch to false:

 defaults write com.apple.iTunes DeviceBackupsDisabled -bool false

For disabling full iTunes backups in Windows, please see these instructions.

free up space on your hard drive

delete iTunes backups

One easy way is to delete the old iTunes backups you're storing. See the "Deleting a backup in iTunes" section of the Apple support article linked here, which I will quote below:

If you want to delete a backup created by iTunes, follow these steps:

• Open iTunes Preferences:
  • Windows : Choose Edit > Preferences
  • Mac: Choose iTunes > Preferences
• Click Devices (the iOS device doesn't need to be connected).
• iTunes will show the phone number, IMEI, and serial number of the backed up iPhone when you position your mouse pointer over a backup (iTunes shows only the serial number for iPad and iPod touch). You can use this to find the backup you want to delete.
• Select the backup you want to remove and click Delete Backup.

5 Quick Tips to Free Up Disk Space in Mac OS X

See the article linked in this subheading for easy ways to clear space on your hard drive if you have a Mac. For clearing up free space on Windows, try this guide.

Monolingual

Another reasonably painless way to free up hard drive space is to use an open source utility like Monolingual to remove unnecessary language resources from OS X, which by itself can free up hundreds of MB.

Other recommendations

You can view your video in the iOS native media player without transcoding

Subler is a utility designed specifically for adding subtitles to video files. It will also, however, simply copy and rewrap, and not transcode, the AVC (h.264) encoded video wrapped in mkv to a friendly format, and it will transcode the audio from ACC to AAC if necessary. Further, it will also optimize the location of the mpeg-4 atom in the resulting file for iTunes friendly use. It uses a friendly drag and drop paradigm. Download Subler, unzip into your Applications folder and launch Subler. Type command-n to begin, and drag your mkv file into the window, and choose from the simple available options to convert your mkv file without transcoding. Then import your new mp4 file into iTunes and sync to your iOS device.

For Windows systems, MkvToMp4 is an application that similarly will reformat your mkv to mp4 without transcoding. Whether the resulting mp4 file will be friendly to iTunes remains to be seen, but it is worth a try to be able to losslessly convert video files from one format to another.

Alternatively, this bash script uses ffmpeg, SublerCLI and HandbrakeCLI to batch rewrap, transcode or otherwise convert video files of various codecies and iTunes/iOS incompatible wrappers to iTunes/iOS friendly formats, automatically choosing a method that retains the best possible quality resultant file. It, however, takes bit of reading and understanding the script to get it to install its dependencies. Also it will take a lot of time to complete processing if set upon a lot of files requiring HandBrake transcodes, and while doing so eventually eat up all your free memory in the process. It is very covenient once it is working and set in your $PATH, will eat through directory structures converting unfriendly video formats where it finds them, and nondestructively will place original files in your ~/.Trash so you can preview the resultant files before eliminating the originals.

Technically, you can use bash scripts on Windows if you first install Cygwin. The script linked above would likely need some adjusting to work under Cygwin, but if learning a little bash doesn't kill you, then it will only make you stronger. ;-)