I've always been frustrated with Google Maps' biking instructions. There are some major trails by where I live that are attached to communities by little 50 foot extensions, but the extensions aren't documented. As such, when you search directions from the neighborhood to another part of town, it doesn't use the obvious MUP that's right there. If anybody is looking to move into the area and is interested in biking or walking anywhere, the connection of the trail to the neighborhood is hidden.

I don't know if I'm late to the game on this, but I had never seen anything about it online anywhere… you can edit the public maps yourself. If you open up Google Maps, in the bottom right-hand corner there's 'edit in google map maker.' You can select 'Add New -> Roads Rivers and Parkways -> Trail/Path and just lay down where the bike path is that isn't documented. Like Wikipedia, there's a peer-review process from other users. Typically within a few hours edits are added, and within a few days, the trails are included in the direction finding algorithms.

As an aside, you can go in and review changes that other people have made. These range from addresses to building locations to points of interest.

In the past couple of days I've added 2 miles of trails just to my little town. I think it helps document the presence of bikeable areas, which is important in getting people to go out and try it sometimes… plus seeing Google Maps updated with stuff that YOU put in there, is pretty sweet.

Google actively (maybe not so actively) solicits public input for corrections, and suggestion. There's a link when you go to a directions page, asking people to report problems. If you use the link they'll make additions or changes to the map reflecting them (after verification).

They also seem to have a tracking system for those who suggest changes, and with a number of accepted changes seem to raise your credibility standing and respond more quickly.

I've found that if there is a MUP then Google Maps ALWAYS choses this route. Too bad there isn't a way to unselect routing on MUPs.
I prefer roads most of the time.

Also it will route to unpaved roads which I sometimes don't like to ride with my road bike. The only way I've been able to determine if the road is paved or gravel is using street view.

You say ALWAYS, but IME it's not so. It probably varies with area, but I find that it won't go far out of the way to use an MUP, so it's easy to avoid MUP routing by using start and ends off to the side of the path.

It's also easy enough to modify the proposed route by drag and drop.

I don't use google maps for my local area, except to calculate miles, but have to say that it does a decent job picking the same routes I would for many routes. I checked my daily commute which I do one of 3 basic ways, and Google maps nailed one of them down to the last turn.

Otherwise, I'm old school and prefer to use regular maps for route planning far from home. Maps show other info, such as rivers, and road type that I can use to gain insights to terrain and traffic volume.

Like any single tool, Google isn't perfect for everything, and is seriously lacking in some cases, but it's pretty decent overall.

There is a app from google(on android, anyway) that allows your phone to record a trail/path via GPS and upload it. I don't really think their GPS coordinates match my area well(the street view certainly has some GLARING issues), but it's an option.

While I could just do it and find out, are they really going to verify the paved BLM road in the middle of nowhere that their map doesn't show, or are they just going to eventually take my word that it exists? (Satellite view doesn't show much of it because of tree cover.)

I've found them to be pretty good about accepting routing suggestions, but sometimes it does take awhile for them to appear. If possible I'd suggest including a URL to some official BLM map in the comments when you input your suggestion to add to your credibility.

Your best bet is to use Open Steet Maps or Open Cycle Maps. Depending on where you live, OP, there could be substantial additions to OSM that is not found on Google Maps. OSM can also be used with the Garmin.