UPDATED ANSWER
You can also try making a List box instead of a checkbox list. Here is the code and again it has no performance issues.
<?php
    if( isset($_POST['chk']) ):
        echo '<pre>';
        var_dump( $_POST['chk'] );
        echo '</pre>';
        die();
    endif;
?>
<!DOCTYPE HTML>
<html lang="en-US">
<head>
    <meta charset="UTF-8">
    <title></title>
</head>
<body>
    <form action="test.php" method="post">
        <select name="chk[]" multiple style="height: 400px;">
        <?php
            for( $i = 0 ; $i < 10000 ; $i++ ):
                echo '<option value="' . $i . '">' . $i . '</option>';
            endfor;
        ?>
        </select>
        <input type="submit" />
    </form>
</body>
</html>
ORIGINAL ANSWER
I tried to create a page to understand the browser behavior and it works perfectly fine without any performance issue for 10,000 checkboxes.
Successfully tested on Firefox 10 and Chrome 17.
This is the code:
<?php
    if( isset($_POST['chk']) ):
        echo '<pre>';
        print_r( $_POST['chk'] ); //simply print the array
        echo '</pre>';
        die();
    endif;
?>
<!DOCTYPE HTML>
<html lang="en-US">
<head>
    <meta charset="UTF-8">
    <title></title>
</head>
<body>
    <form action="test.php" method="post">
        <?php
            for( $i = 0 ; $i < 10000 ; $i++ ): //adjust this number to whatever number of checkboxes you want
                echo '<input type="checkbox" name="chk[]" checked /> Checkbox ' . $i . '<br />';
            endfor;
        ?>
        <input type="submit" />
    </form>
</body>
</html>