Mr. Smalls is only about a half mile from the Millvale Trailhead. But, the connection from 40th Street is not good. If you go that route, you can ride down from 40th into Millvale, but you might want to walk UP the goatpath on the river side of the street at the end of the evening (cars won't be expecting to see you there, there is construction, etc.)
An alternate route that is worth considering is to take the 31st Street Bridge, and pick up the Millvale Trail near Washington's Landing (where the new section starts).
At Millvale Riverfront Park, follow the path all the way to the stop sign. Turn left under the railroad bridge, cross railroad tracks etc. At stop sign (which is where you would be coming down if you came across the 40th Street Bridge) continue straight (towards big Family Dollar sign). Stay on that road about 3 blocks. Look right, and when you can see the Millvale Police Department/Borough Building on the cross street (or when the street addresses approach 400), turn right (uphill) for one block. Mr. Smalls will be on the left, on the far side of Lincoln. By bike, it is certainly less than ten minutes from the trail, and probably more like 5 minutes. These will be two way streets, single lane in each direction, with very little traffic. I think there is a street light at just about every corner. I also think the posted speed limit is like 25 mph. Very confortable for riding. You might want to be sure to check your lights, just to be safe. I think they have that old time "character" street lighting, which is not terribly bright.
If you head out of the park where the trail is, and head for the Family Dollar sign, it will be hard to get lost. There are two parallel streets that have businesses on them. You'll be on one, Mr. Small's will be one block to your right. The streets are only about 6 blocks long, and at every corner they have signs that point to area businesses. I think they are blue, and I'd bet that there will be one for Mr. Small's on the street you are riding on......