Well, it does slow down if the iPhone shows 0 Gb as available. However, that doesn't really mean there is no space available at all. iPhone itself constantly deletes cache/temp files (you will see apps shown to be "cleaning" time to time). During this "cleaning" process, apps can exhibit stutter and lag (opening, multitasking, updating/refreshing contents, etc)
So yes, low storage can slow down the device. If a certain app has to "clean" itself in order for another app in use to store cache/temp files, you might see certain amount of lag and stutter.