...however the many worlds interpretation would solve all of those paradoxes. So the end result would be that while you could communicate instantly the information you sent would end up in a parallel world.
Ok, please clarify what you mean by a parallel world, because I feel like you're using it in a non-standard way as far as MWI goes. MWI predicts that universes keep branching. Once decoherence happens, they are cut off from each other. So, of course, you can't mean that the message goes into a universe that branched away from the current one at an earlier
point (that would also be silly because then, in the receiving universe, a message would just come right out of nowhere!) So that leaves parallel world to mean a later
evolution/branch of the current universe, but not the same one that "you" end up in. But that would mean that the sender of the message necessarily exists in all
of those universes' pasts, and that's not really a parallel universe in the sense that it would allow you to avoid any side effects of killing your grandfather.
In any case, we're talking two different things here. FTL-related time travel is a relativistic effect, it has nothing especially to do with entanglement (except that it's sometimes implied that entanglement is one way that FTL would be possible, but I say to that there are *very* good reasons to believe the No-Communications Theorem), nothing to do with the double-slit experiment, and nothing to do which interpretation of QM you go with (there isn't even a known way of testing between MWI, the Copenhagen interpretation, de Broglie–Bohm, etc. If what you were saying were true, then you would have just discovered one. Incidentally, this would almost guarantee you the Nobel Prize.)
Rather, FTL time travel happens because of 2 main, experimentally verified effects of relativity: time dilation, and the constant speed of light in any inertial frame
-Time dilation: we know that as an object accelerates close to that of light, time dilates. In other words, while a small amount of time passes on the near-light-speed object, a large amount of time passes in the relatively non-accelerating inertial frame.
-Constant speed of light: we also know that no matter how quickly you are moving, if you measure a beam of light in a vacuum, it will always be moving at exactly the speed of light. Even if you're moving at 99% the speed of light, the photons will seem, to you, to be moving at the speed of light relative to you, while a stationary observer will observe a very slight difference in the beam's speed and your speed (only 1%).
Ok, so let's put it together.
You are racing a photon in your spaceship. You and it are going 1 light year in distance. Your spaceship is capable of traveling at 99% the speed of light. You and the photon set off at the exact same moment. What happens?
From your point of view, the photon shoots ahead of you, since relative to you, it's moving at the speed of light. It necessarily must get to the finish line considerably before you, because you know it's flying away *much* faster than you. By the time you get to the finish line, you don't even smell its space dust. But, from the point of view of people watching from bleachers set up along the course, you do trail the photon, but not by much (to them, it's moving at the speed of light, but you're moving at 99% the speed of light, so not bad).
So when you finally get to the finish line and ask, "How much did that photon beat me by?" what are they going to say, that it got there just before you did, or waaay before? Well, this is where time dilation comes in. Even though you've been racing for, in your opinion, just a bit over a year (one light year at 99% the speed of light would take just over a year of your time to cover), to the people at the finish line, a century has passed! Therefore, they're going to say the light beam *did* get there well before you (only one year after the start of the race, and you showed up around 99 years later). I'm ignoring length contraction and the impossibility of defining simultaneousness in separated regions of space, both of which are necessary for a full picture, but this is enough to show why time travel is inherent in FTL: if you were going *faster* than the photon, the only way you'd agree with people at the finish line is if you traveled backwards in time and arrived before you left. Because, from your point of view, the photon still shot ahead of you (constant speed of light, remember), but to everyone else, you shot ahead of it. I don't see how MWI would change a thing in this thought experiment.