After looking through several books from Deadlands Reloaded and Deadlands Classic, I am surprised to say that there does not seem to be any official mention of how big a maze runner is. There also seems to be very few pictures of a maze runner itself, which is odd given its importance in that area of the Weird West. Another answer mentioned that there is the Deadlands d20 'Rats in the Maze' adventure that includes a maze runner figure flat, but as noted there is no grid and it's not clear if it is intended to be to scale (8" = 48' for the length of the ship seems a little small, so it sounds to me like they just made it as large as the paper would allow them).
However, there was a 4 issue Deadlands comic anthology series published in 2011 and early 2012 and the last issue, Black Water, took place in the Great Maze with the characters boarding a maze runner at one point. From the images, we can see how large this particular maze runner was:
Notice the man standing on the lower dock near one of the signature paddle wheels, which gives some perspective. Given his size in relation to the maze runner, I'd guess that it's at least 20 feet from the dock he's standing on to the deck, and the runner itself is maybe 125-150 feet long (20-25 battlemat inches).
The deck is pretty spacious too; the characters seem to have a lot of room (about 6 feet between the railing and the structure, which is conveniently equal to 1 battlemat inch):
In relation to the Great Maze itself (or this particular area of it), the maze runner has room, but not much of it. It would be difficult to have two try to pass each other. Notice also the size of the two lifeboats and the size of the man standing at the front of the maze runner.
Below decks there is enough space for a dining area (and presumably living space as well) large enough for nine people...and a horse!
I would imagine that maze runners come in all sizes depending on their purpose (passengers, cargo, etc.) and how wide the straits will be that they're traveling through, much like the real world steam boats that they are based upon. The Smith and Robbards 1880 Catalog says that a maze runner requires 3 crew and can take up to 5 passengers, so the maze runner in the pictures is probably a bit larger than average since it can take more passengers.
If we assume that the size of the maze runner in the 'Rats in the Maze' adventure is to scale and an example of a smaller maze runner and the one in the comic is a larger one, then maze runners typically range from 48 feet to 150 feet long (8 to 25 battlemat inches). Personally I'm inclined to lean towards the larger figure given the size of steamboats I've seen, but I imagine you could make it anywhere within that range, or a bit beyond, if you wanted.