In a nutshell, the trick to longer distance races is to train at those distances. To run a 10 k race, work your way up to 8 or 9 k regularly before your race. The same holds true for longer distance races. To successfully run a half-marathon, train so that your training runs have increased to 15 to 18 k in month or so before the race. When training for marathons, the longest training run is about 40 km. That run takes place four to six weeks before the race. Most training plans take into account the fact that most of us have jobs. Distances are between 5 and 15 k during the week with the long run (working up to 40 k) on the weekend.
Speed doesn't play a whole lot into it except in learning how to regulate it. Consistency in pacing is more important.
Being outside is great, but unless your race is hilly training on a treadmill is fine especially for the weekday runs. Make use of the incline.
I really, really like Hal Higdon. Here's his beginner novice plan for a marathon. You can see how the distances increase. The plans for more advanced runners presume you are already running substantially longer distances.
And good luck.