ipodで再生するための2つの.mp4ファイルを結合するソフト

>itunesから削除するにはどうすればよろしいでしょうか。

至極簡単です。
iTunesの「ビデオ」で表示されている不要なビデオをワンクリックしてdeleteキーを押すだけです。
元ファイルが既に無いのであれば何の警告もなく削除されます。
元ファイルが有る場合はミュージックストアで購入したものかも知れんとか何とかの警告が出て、キャンセル、ファイルは残す、ファイルをゴミ箱に入れるの3つの内から選択します。

対応フォーマット:H.264ビデオ（最高768 Kbps、320×240、毎秒30フレーム、最高レベル1.3のベースラインプロファイル（最高160 Kbpsの AAC-LC）、48 kHz、.m4v/.mp4/.movファイルフォーマットのステレオオーディオ）、

MPEG-4ビデオ（最高2.5 Mbps、480×480、毎秒30フレーム、シンプルプロファイル（最高160 KbpsのAAC-LC）、48 kHz、.m4v/.mp4/.movファイルフォーマットのステレオオーディオ)←AppleのHPより抜粋。
これに合致していますか？
ビットレートが高すぎるとか、画像サイズが640x480等になっていませんか？
これらはQuickTimeやiTunesでは再生出来ますがiPodでは不可です。

もう一つ、ダメ元で拡張子を.m4vにしてみて下さい。
たまに同じファイルでも.mp4では再生出来なくて.m4vなら再生出来る時が有りますから。←理由は不明ですが、経験あり。

結合出来ればいいんですよね？

丁度よいものを見つけました。
AddMovieと云うフリーウェアです。
QuickTimeで扱えるファイルは全て対応しているそうです。
英語ですが全く難しい所は有りません。
結合したいmovieを登録してAddボタンを押して保存先を設定するだけです。

参考URL：http://www.limit-point.com/Utilities.html#AddMovie

QuickTimeの場合別名保存しようとすると必ず.movになりますし、フラット化とかで結構時間かかりますね。

それでもうちではエンコードと同じほどもかかったりしませんが(容量によって全く違うがせいぜい1～2分。)

MPEG Streamclipを使ってみて下さい。
http://www.squared5.com/
OSがハッキリしませんが、MacOSXかWindowsXPなら大丈夫です。
英語ですが特に難しくはないと思います。
File→OpenFilesで対象ファイルを選択(複数選択出来ます。)
FIle→Save as・・・で保存先とファイル名を設定して実行します。

因に私は試験用に数十秒のファイル(H264/AAC)を2つ結合させましたが数秒で終わりました。
(PMG4Dual1.25GHz MacOSX10.4.7)