Do we really know whether the Q can time-travel as opposed to just having the ability to set up good illusions, and possibly take people out of time?
Don't we only have his word for it? Is there some hard example that shows Q really can travel and alter the timeline?
Yes. In the episode "Death Wish", the Q known as Quinn (AKA Q2) takes the Voyager back in time to the Big Bang itself.
TUVOK: Captain, based on our readings, it appears that we have been transported back in time to the birth of the universe.
Janeway looks sharply at Q2 who smiles as he watches the viewscreen... acknowledging.
Q2: Very old hiding place.
ANGLE (OPTICAL) There's a flash, and Q1 appears near Torres.
Q1: (beat, to Q2) I know all the hiding places, Q. I hid here from the Continuum myself once.
Even if Tuvok was somehow mistaken about his readings, since this time jump was made in an attempt to evade another Q (who presumably would be in no way fooled by a mere illusion) it makes no sense for this to have been a trick.
The Q continuum is an extradimensional realm, and as such exists outside the space-time continuum of the universe as we perceive it.
It is highly likely, as extradimensional beings, that the Q can travel through time in our universe. Our universe is either a spacetime submanifold of the larger Q continuum or are two disconnected universes. In either case, the Q seem to be able to enter our spacetime manifold at a point of their choosing ("point" meaning a location in space and time).
Memory Alpha has the same opinion:
The Q Continuum was an extradimensional plane of existence inhabited by a race of beings known as the Q. The term could also refer to the Q society itself.
As a race, the Q were immortal, but not absolutely omniscient or omnipotent, just possessing the ability of instantaneous matter-energy transformation and teleportation, as well as the ability of time travel. Their apparent abilities included moving entire asteroid belts and stars, creating alternate timelines, and affecting universal states of nature such as the gravitational constant.
Note that these are just my opinions and the opinions of whoever contributed to the Memory Alpha entry.
Since the Q are for all intents and purposes omniscient and know exactly what humans have and have not achieved, there is no denying that the Q would know that humans themselves have achieved time travel in the past (a feat performed twice by the original Enterprise crew). Therefore, the Q would know how to achieve at least one form of time travel.
Since the question was "Do we really know whether the Q can time-travel?" (rather than, "Have we seen an actual instance of Q travelling through time?"), the answer would almost certainly be Yes.
In terms of canon, we see in the series finale of TNG ("All Good Things...") an example of Q travelling through time, at least seemingly. He and Picard travel between four different time periods: the present; seven years prior; twenty-five years into the future; and far into the past to a time when life was only beginning on Earth:
On the face of it, there is no indication that these travels were an "illusion". On the other hand, since only Picard remembers what happened, it could have been an elaborate illusion. The sentiments of the official StarTrek.com entry on the episode suggest that it was "real", however:
Picard is returned to the moment his adventure began, coming from the Turbolift in his bathrobe. He shares his experience with the crew, using what he has learned about the future to forge a new, closer relationship with his dearest friends.
(Source)
It would seem to me the answer can't be a complete yes, as it appears the Q can't see extremely far into the future, as Q notes in "Hide and Q" there is a future that is beyond even their ability to conceive.
Riker: Eons! Have you any idea how far we'll advance?
Q (COMMANDER): Perhaps in a future you cannot yet conceive... even beyond us. And so, we must know more about the human condition. We have selected you, Riker, to become part of the "Q"... to bring that human need and hunger to us so that we may understand it.
Restating other answers, but Star Trek canon is full of examples of humans accidentally or intentionally travelling through time; the time travels are always depicted as "real" (never hallucinations or of ambiguous "reality") and usually explore some aspect of visits to the past influencing the "present" state (or affecting the timeline). This makes time travel an established fact within Star Trek canon, and in a number of cases (e.g. TNG "A Matter of Time") accomplished by a device of human (or at least mortal humanoid) construction and control. See this page for a more comprehensive list
Given all that canon, it would be hard to imagine that the Q could not do as much or more with time than humans or "lower forms" (in Q-speak) have done, either accidentally or intentionally.
For what it's worth: there is a DS9 story of Sisko as a 1950s science fiction writer, but this is clearly revealed to be a "vision"/hallucination.
