[INFO] Bitrate settings

[Selur]

Okay,... first problem I have is that bit rate sadly does not say anything about the amount of details or the quality of the source.
Also, I would not use bitrate, but quality based encoding.
(with vbv I see no real point in using bit rate based encoding unless you need to hit a specific file size and the the question about bit rate is answered by the target size)
That said, for the sake of argument, let's assume the source was optimally compressed, and re-encoding the source would also be optimally done.

If the source video is 1000kbps 640x480 25fps black & white mp4 video, and I colorize the clip with Deoldify, do I have to increase the bitrate to accommodate for the color?

Assuming your source has no chroma info and thus effectively is 4:0:0 YUV content, just be adding color you have more information:
4:0:0: Only luma information is stored and(Y: 8 bits, U: 0 bits, V: 0 bits) requires 8 bits per pixel
4:2:0: Chroma subsampled both horizontally and vertically by 2 (Y: 8 bits, U: 2 bits (averaged over 4 pixels), V: 2 bits (averaged over 4 pixels)) and requires 12 bits per pixel.
4:2:2: Chroma subsampled horizontally by 2 (Y: 8 bits, U: 4 bits (averaged over 2 pixels), V: 4 bits (averaged over 2 pixels)) and requires 16bits per pixel.
4:4:4: Full chroma and luma information for each pixel(Y: 8 bits, U: 8 bits, V: 8 bits) and requires 24 bits per pixel.
So without compression, going from 4:0:0 to 4:2:0 would increase the amount of data by 50%.
Depending on the target format the used and encoder and its settings, the actually needed data, i.e. when compressing losslessly should be way lower.
(my gut feeling, for a modern lossy encoder&format maybe 10%)

If I upscale the same (now colorized) video to 1920x1080 (letter box), what would be the recommended bitrate?

Going from 640x480 to 1920x1080 would increase the number of by a factor of 6.75, but since you usually don't have that much more information in a 1920x1080 source, I would suspect more like a factor of 3.5 to 5 on natural content. (will be way less on cartoons&co)

If I use rife 2x (now colorized and upscaled) video, what would be the recommended bitrate?

Increasing the frame rate and by a factor of 2 in theory would add 2 times the amount of information. But the actual gain in information is way less, so I would probably expect an increase of maybe 20% of needed the required output size / bit rate.

=> I would not advise using bitrate based encoding, but if you want/must, hopefully the above helps a bit about the general.

Cu Selur

Ps.: if you used lossless intraframe only, compression the increases would be higher, since basically no motion compensation (basic MPEG ideal) would be used.