In order to get the flag -depth 4 work, you should use also the flag -colors with the desired color depth (in your case 16).

The following command should generate an icon with the same size of the original:

$ convert -flip -colors 16 -depth 4 wikipedia.ico flipped.ico

I have tested it on Windows and the flipped icon has the same size of the original.

See also this forum.

In order to get the flag -depth 4 work, you should use also the flag -colors with the desired color depth (in your case 16).

The following command should generate an icon with the same size of the original:

$ convert -flip -colors 16 -depth 4 wikipedia.ico flipped.ico

I have tested it on Windows (ImageMagick version 7.0.3-Q16) and the flipped icon has the same size of the original.

See also this forum.

-- Update --

I've tested the command above on a Debian machine (ImageMagick version 6.3.7-Q16) and on a CentOS machine (ImageMagick version 6.7.8-9-Q16), and in both cases I obtained an icon with the same size of the original (2734 bytes).

Just as reference, the output of different versions of identify is different.

identify 6.3.7

identify wikipedia.ico
wikipedia.ico[0] ICO 48x48 48x48+0+0 DirectClass 8-bit 2.66992kb
wikipedia.ico[1] ICO 32x32 32x32+0+0 DirectClass 8-bit 2.66992kb
wikipedia.ico[2] ICO 16x16 16x16+0+0 DirectClass 8-bit 2.66992kb

identify 6.7.8-9

identify wikipedia.ico
wikipedia.ico[0] ICO 48x48 48x48+0+0 4-bit DirectClass 2.73KB 0.000u 0:00.000
wikipedia.ico[1] ICO 32x32 32x32+0+0 4-bit DirectClass 2.73KB 0.000u 0:00.000
wikipedia.ico[2] ICO 16x16 16x16+0+0 4-bit DirectClass 2.73KB 0.000u 0:00.000

identify 7.0.3

identify wikipedia.ico
wikipedia.ico[0] ICO 48x48 48x48+0+0 4-bit sRGB 2.73KB 0.000u 0:00.000
wikipedia.ico[1] ICO 32x32 32x32+0+0 4-bit sRGB 2.73KB 0.000u 0:00.000
wikipedia.ico[2] ICO 16x16 16x16+0+0 4-bit sRGB 2.73KB 0.000u 0:00.000

Are you using an updated version of ImageMagick?