I've found MJPEG to be more bandwidth intensive, especially as the resolution increases however, since its flushing the full frame every time (whereas with GIF you could send just the differences between frames).
Would depend on what you're sending. If you take make good advantage of gif interframe transparency and are just sending small updates the result could be very small. That still leaves the problem unless I'm mistaken of the browser hanging on to the old gif frames.