Решил таким образом. Game.exe и Update.exe закроются, но останется открыта консоль из Update.exe и будет независимым процессом.

Melz, В Windows я делал обновление похожим образом, но там при закрытии Game.exe, Update.exe не являлся для него дочерним и существовал далее.

Код Game.exe:

static public void Run(Version version)
		{
			ProcessStartInfo psi = new ProcessStartInfo() {
				WorkingDirectory = Path.GetDirectoryName(AppDomain.CurrentDomain.BaseDirectory),
				FileName = "/usr/bin/mono",
				Arguments = String.Format("Update.exe -exe \"{0}\" -ud \"{1}\" -v \"{2}\"", Process.GetCurrentProcess().ProcessName, Config.ServerUrl, version)
			};
			Process.Start(psi).WaitForExit();

			MainForm.Instance.Close();
		}

Код Update.exe:

public static int Main(string[] args)
		{
			ParseArguments(args);
			String tmpFile = Path.GetTempFileName();
			File.Copy("update.sh", tmpFile, true);
			Process.Start("xterm", String.Format("-e sudo bash {0} {1} {2} {3}", tmpFile, AppName, UpdateDomain, VersionToInstall));

			return 1;
		}