Upload to a GP Service is sort of a multistep process.
You're correct, you do want to use a "file" (GPDataFile) as the input parameter.
If you're using Destkop to consume the service, desktop will send the file to the server.
If you're using a webapp, you're responsible for getting the file to the server. (Server at 10.1 has some upload capabilities in REST you can leverage. If using 10.0 or prior you'll need to devise a way to get the file to the server your self)
Once the file has been upload, because you're talking shape file, you'll have to unzip it. (shapefile being multiple files to make up a single one).
With it unzipped, you can then pass the file to your service.
Based on your error - your file didnt upload, or you never sent it. Whats the client to consume the GP Service - a web app?