[OED:] Etymology: For forth with (preposition), = earlier forth mid, along with, see forth adv. 2c. The adverb forthwith originates from this phrase, the preposition being used absol. or with ellipsis of its regimen.
[forth adv. 2c] †c. In early Middle English forth mid, later forth with = ‘along with’. Also absol., along with him, them, etc.: at the same time with something else.
at the same time ... does not mean 'immediately'. Per this answer, with can mean 'with' or 'against'; so I don't know how to disambiguate it.
Here's my guess at the etymology: Suppose you want to proceed forth with X. Then X may need be completed immediately. Please allow me to verify, to avoid deluding myself with false etymologies.