You have a MultiWire Branch Circuit - MWBC. That saves a wire, which is great.
You are installing GFCI. GFCI functions by monitoring for a difference between outgoing (so to speak) and incoming power. That is either between two hots (on a pure 240V circuit) or between hot & neutral (on a 120V circuit) or combining the two hots & the neutral (on a 120V/240V circuit, which is essentially what an MWBC gives you). In order to include the neutral in the equation, the neutral needs to be connected to the GFCI instead of simply to the neutral bar. In addition, since the neutral is shared, it needs to go to "both" GFCI. But that doesn't work, because each GFCI doesn't know which "part" of the neutral current belongs - and it can't because with an MWBC that neutral is not going to be exactly split.
End result, you need a GFCI that is specifically designed as a double-breaker. It takes both hots and the neutral into one unit that looks to see that the net difference between the hots matches the neutral. 1/2 the circuit 10A, the other 1/2 0A - then neutral = 10A. 1/2 the circuit 10A, the other 1/2 10A - then neutral = 0A, etc. Simply can't do it except as one integrated unit.
The exact breaker will vary by manufacturer. But it will be something like this:
Sample image is from Amazon. Be careful where you buy your breakers (and similar items). If possible, buying "hands on, local" is preferred so you can make sure you get the right product (depends on your particular panel) and legitimate product (Amazon, depending on a number of factors, will sometimes substitute "equivalent" or used or other problem items, particularly if you don't know the details of how to order carefully.)
You don't need handle ties this way, because double breakers are, by definition, common shutoff.
While nuisance trips on GFCI devices should be minimal-to-none, your mileage may vary. But there is an additional real concern with an MWBC: Because the two breakers are treated as one (for both overcurrent and GFCI), a GFCI trip on one side of the MWBC will shutoff power to the entire MWBC. Toaster on one, coffee maker on the other. Spill coffee on the wrong parts and trip GFCI - the toaster will go off too! Not a big deal most of the time, but if one of the circuits has a clock then now you need to reset it, etc.