In addition to normal GIF compression on each individual image, animated GIFs can optionally apply math operations between the next frame and the already on-screen frame, and put smaller images in smaller areas on the image canvas.
So let's say you have an animated GIF with 10 frames, and it's a black and white stick figure walking across the canvas. The first image would be complete, fill the canvas, and have all the information needed as if it were a stand-alone GIF. The next "frame" might only consist of a smaller box that only updates the area that has changed.
With video animated gifs, this is more complicated. Due to dithering you often find that the entire frame changes, so it's going to be larger.
Some GIF optimization software can make significant optimizations if it starts off with a good video source. Further, the software can make some tradeoffs to improve (decrease) size but by compromising the animation - perhaps worse dithering, for instance.
If you start off with such a GIF, though, and change it, even in some small way, you can't necessarily expect the software (in this case photoshop) to be able to apply the same optimizations because it lacks the original source video. Further, it may not even store it internally in a way that allows it to recreate the original GIF with its optimizations. Try opening the animated GIF, then exporting it as a new animated GIF without making any changes. It's possible that the size increases simply because it's not using any optimizations and is storing each full frame.
Once you change the frames, you'll find that the size will increase anyway, even with optimizations. This is particularly true if you use an alpha channel and have some of the logo see-through or as a watermark with translucency.
You may be able to recover some of the optimizations by running it through a GIF animation optimizer software after photoshop, and a lot of people do this anyway, because photoshop values quality and pixel perfection over size.
The ideal solution, though, is to take the original video (not the GIF, but video file), apply the logo/watermark, and then use a GIF animation program specifically designed to optimize for size to do the conversion. Skip photoshop entirely.