As said, depends on what the difference between linear and nonlinear is. If the Prophets perceive time as occasionally accelerating, occasionally slowing down, it's still "nonlinear" in the mathematical sense: the curve of speed-of-time vs. passage of time is not a straight horizontal line but, well, curved (or the curve of Prophet time vs. our time is). This wouldn't be particularly exotic yet, and wouldn't ruin causality or anything.
But the time the Prophets experience cannot be a mere dot or a vertical line on such a diagram, or they would never learn anything, or would learn everything at once. And it needs to loop back on itself in funny ways to explain why Sisko is created only after he is encountered, in terms of the horizontal axis. Still, "funny" by no means equals "patently impossible": functions that loop back are merely more complex than functions that do not.