Parece que você está ficando sem i-nodes. Mostrar saída de df -iht ext4
.
Eu também tive um problema com a remoção de um diretório no EXT4 contendo ~ 1 milhão de arquivos (linux kernel 3.0, IIRC). Qual é a versão do kernel no seu caso?
Por fim, sugiro usar o Reiser3 - ele não tem limites de i-node em tempo de formato e, no caso mencionado, parece ter resolvido o problema também.
UPD .: Para aqueles que se perguntam se o Reiser3 é suportado em:
cd linux-stable/fs/reiserfs && git log --pretty='format:%aD %s' . | head -n20
Tue, 10 Jan 2012 15:110:11 -0800 reiserfs: don't lock root inode searching
Tue, 10 Jan 2012 15:11:09 -0800 reiserfs: don't lock journal_init()
Tue, 10 Jan 2012 15:11:07 -0800 reiserfs: delay reiserfs lock until journal initialization
Tue, 10 Jan 2012 15:11:05 -0800 reiserfs: delete comments referring to the BKL
Mon, 9 Jan 2012 12:51:21 -0800 Merge branch 'for_linus' of git://git.kernel.org/pub/scm/linux/kernel/git/jack/linux-fs
Wed, 21 Dec 2011 21:18:43 +0100 reiserfs: Force inode evictions before umount to avoid crash
Wed, 21 Dec 2011 17:35:34 +0100 reiserfs: Fix quota mount option parsing
Wed, 21 Dec 2011 20:17:10 +0100 reiserfs: Properly display mount options in /proc/mounts
Wed, 7 Dec 2011 18:16:57 -0500 vfs: prefer ->dentry->d_sb to ->mnt->mnt_sb
Tue, 26 Jul 2011 02:50:53 -0400 reiserfs: propagate umode_t
Tue, 26 Jul 2011 01:52:52 -0400 switch ->mknod() to umode_t
Tue, 26 Jul 2011 01:42:34 -0400 switch ->create() to umode_t
Tue, 26 Jul 2011 01:41:39 -0400 switch vfs_mkdir() and ->mkdir() to umode_t
Mon, 12 Dec 2011 15:51:45 -0500 vfs: fix the stupidity with i_dentry in inode destructors
Fri, 9 Dec 2011 08:06:57 -0500 vfs: mnt_drop_write_file()
Wed, 23 Nov 2011 11:57:51 -0500 switch a bunch of places to mnt_want_write_file()
Fri, 28 Oct 2011 14:13:29 +0200 filesystems: add set_nlink()
Fri, 28 Oct 2011 14:13:28 +0200 filesystems: add missing nlink wrappers
Tue, 25 Oct 2011 12:11:02 +0200 Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/jikos/trivial
Thu, 15 Sep 2011 15:08:05 +0200 Merge branch 'master' into for-next