That's a tough one. All languages (previously) in existence are in essence linear, because they are phonetic representations of human experience. Even when describing the past or the future, language does so in a linear form. Also, any human language is itself subject to time, with one phoneme uttered after another. In addition, the grammars of some languages are very restrictive to allow expression of effect preceding cause, etc. For example, Indo-Germanic languages cannot have verbs without a subject and the subject must precede the verb. So looking at natural languages it is clear that some are better suited to express time paradoxes etc. than others.
Probably the best candidate languages to extend or base a conlang on would be those languages that do not change sentence structure for singular vs plural, present vs past or future, affirmative vs negative, certain vs conditional, etc. Japanese for example would be a good candidate. To change all of the aforementioned sentence parameters you would just use suffixes, e.g. -ta for past tense, -tachi for plural, -yo for conditional, etc. It could therefore easily be extended with suffixes to express time paradoxes, timelines, etc.
Another language that meets the conditions of unchanging sentence structure related to time & conditions would be Chinese (Literary Chinese to be exact, Modern Chinese would be a bit more problematic due to its compound phrases). This is a monosyllabic language where word meaning is based on tone. Chinese currently has 4 tones. You could add modulations to these tones to express time travel related conditions and effects. But unless you've been brought up in this language it would be extremely hard to learn (just learning to distinguish the current 4 tones in all circumstances is already a daunting task for a non-native speaker unless you're also musically inclined).
If you want to construct a conlang that is not based on any existing language, a good candidate would be a language that is based on harmonics (i.e. multiple frequencies uttered at the same time). Different harmonics could represent different time-related states. However, human vocal chords are not really up to the task of uttering complex harmonics.
There's probably many other ways to answer your question but here's my 2 cents :)