Why does this happen? Is photoshop creating new information? ... The max size should be no more than 5 * 5 = 25Mb, right?

Your source images are JPG, so it doesn't make sense to compare their sizes with a final uncompressed TIF. (Apples to Oranges.) You will get a more reasonable output size for comparison if you resave your TIF output as JPG. (Apples to Apples.)

Then, when I flatten layers and save again, it reduces to 111 MB [from 650 MB].

Each layer contains pixels that were not present in the original to expand the image to fit parts of the panorama that the other photos cover. These pixels require space to store. Each layer also contains alpha channels to define transparent areas. Since you are using an uncompressed format, this "extra" information takes up a lot of space. Flattening the image discards "duplicate" pixels that aren't visible, as well as the alpha channels.

How can I save it in a format that doesn't lose any pixels, but also doesn't increase in size?

You usually cannot get photos down to the size of JPGs without resorting to lossy compression. You can try PNG, which doesn't support layers and is slower, but usually smaller than TIF. You can also save TIF with lossless compression – the best at this time is Deflate (Zip).

I would use the native format of the software (PSD for Photoshop, XCF for GIMP) while actively working on the image. Then save the final work with JPG quality 99 (Photoshop 12).

My experience has been that the difference between quality 99-100 and lossless is negligible. Plus you have the original source images if it becomes necessary to reprocess. While you would likely want to avoid duplicating work in the future, advances in technology should make future efforts quicker with improved results.