You're just using the focal length as part of a camera model.
All you really care about is exactly what the image you posted depicts - that you can correlate a particular pixel with an angle. If you know the angle to a point of interest from one camera, and you know the angle to the same point of interest from another camera, and you know how far the cameras are apart, then the law of sines can tell you where that point of interest is actually located.
Like I said above - what you really want to know is how a pixel relates to an angle. If you know that your key point is located 15 pixels from the left edge (the right camera in your image), what angle does that make between the image receptor and that key point? That depends on the focal length of the camera. A lot of techniques use the pinhole camera model, and I believe this is sufficient for most cameras, but especially if you wanted to use a fisheye lens or similar then you need to rectify your output image in addition to applying the camera model.
This might be a straightforward process, but it can definitely get complicated in a hurry, especially if you can't find documentation regarding the characteristics of the lens you're using.