The fisheye effect does not come from the wide focal length, but it comes from using a lens that is not rectilinear.
A rectilinear lens is one that, despite the focal length, will still ensure that there is no barrel or pincushion distortion: that all straight lines remain straight, not curved. Technically, it ensures that the image is the image that would be formed by a projection of a scene on a flat plane.
Fisheye lenses deliberately forego worrying about perspective correction or being rectilinear, for reasons such as:
At very wide angles, a rectilinear lens requires bigger, heavier glass and is more expensive. Fisheye lenses are significantly cheaper by comparison.
Just because an image is rectilinear does not mean that is doesn't look distorted: while all the straight lines will be straight and there will be no barrel distortion, the extreme wide angle will still make things towards the edges of the frame unnervingly large and stretched looking. Fisheye lenses minimise this effect at the expense of creating heavy barrel distortion and therefore no longer being rectilinear.
Example (this is a rectilinear - not fisheye - image: all straight lines are straight - demonstrating the odd effect of rectilinear images at very wide angles):
This particular image is probably a rectilinear conversion of a fisheye image. A rectilinear lens this wide, while technically possible, would be very unusual and the lens itself would probably look quite strange.
You can reach greater angles of view with a fisheye lens than you can with a rectilinear lens. A rectilinear image gets more and more stretched-looking as you approach 180 degrees of view, and it is literally impossible for it to have a full 180 degrees of view or more. A fisheye lens can be made which has more than 180 degrees of view.
This is not just a limitation of lens technology but of geometry itself: it is just as impossible to create a 3D computer rendering of a scene with 180 degrees or more of angle of view, while making it rectilinear.