Here are some solutions I know of. Just chose one fits for your situation.
First one: Turning off enforced check in/out. Specifically, go to document library settings>versioning settings>select “no” for “Require documents to be checked out before they can be edited?”. Then upload all your files. After that re-able that requirement.
Note: this solution is a good one under stringent security enforcement condition.
Second one: Using manage content and structure. That is to say 1. Go to “Site Actions” – “Manage Content and Structure”. 2. Navigate to your library. Once all your documents in this library are listed click “select all” icon. 3. Click the “Actions” menu and select Check In.
Note: the drawback of this solution is you need MOSS and it can be done just by administrators.
Third one: SharePoint Batch In. With this tool, you can: 1. Check In multiple checked out documents in document library at one time; 2.Discard multiple checked out documents in document library at one time; 3.Upload and Check In multiple documents in document library at one time.