Installed on unrooted Fire phone with latest FireOS 3.6.8 and worked. Installation require slight tweaking. For some reason I could not see "Garmin/.system" from my pc even though I have my computer folder option to unhide everything. Here is what I did to get the gmapbmap.img and gmapprom.img to the Fire phone using adb.

1. copy StreetPilot_2.35pi_5.0_storage_sdcard0_signed.apk to Fire phone and install.
2. copy file *.img to the phone to "Internal storage/Garmin"
3. run adb shell and move *.img file from step 2 to /storage/sdcard0/Garmin/.system/

Note: you can also use the push command but I was having problem with pushing gmapprom.img to the phone.

Also, I don't think this should matter but I have installed google play on my fire phone which you can find info on it by googling it.